PattySung

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = “ABAB”, k = 2 Output: 4 Explanation: Replace the two ‘A’s with two ‘B’s or vice versa. Example 2:

Input: s = “AABABBA”, k = 1 Output: 4 Explanation: Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”. The substring “BBBB” has the longest repeating letters, which is 4. There may exists other ways to achieve this answer too.

<解題>


class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length();
        int[] char_counts = new int[26];

        int start = 0;
        int maxLength = 0;
        int max_count = 0;

        for (int end = 0; end < n; end++){
            char_counts[s.charAt(end) - 'A']++;
            int curr_count = char_counts[s.charAt(end) - 'A'];
            max_count = Math.max(max_count, curr_count);

            //如果窗口內的字符中非主要字符的總數（需要替換的字符數）超過了允許的最大替換次數 k，則需要縮小窗口
            while (end - start - max_count +1 > k ){
                char_counts[s.charAt(start) - 'A']--;
                start++;
            }
            maxLength = Math.max(maxLength, end - start +1);
        }
        return maxLength;
    }
}

Time: O(n) Space: O(1)

Leetcode-424. Longest Repeating Character Replacement

<解題>