LeetCode 424. Longest Repeating Character Replacement

原題鏈接在這里：https://leetcode.com/problems/longest-repeating-character-replacement/description/

題目：

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most?k?times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and?k?will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2Output:
4Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1Output:
4Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

題解：

類似快慢指針維護substring的方法在Minimum Window Substring里有總結.

隨著runner向前推進找出最高frequency word的count. substring整個長度減掉最大的count 就是需要調換的字符數, 若大于k就移動walker.

Time Complexity: O(s.length()).

Space: O(1).

AC Java:

class Solution {
    public int characterReplacement(String s, int k) {
        int [] map = new int[256];
        int walker = 0;
        int runner = 0;
        int maxCount = 0;
        int res = 0;
        while(runner < s.length()){
            maxCount = Math.max(maxCount, ++map[s.charAt(runner++)]);
            while(runner-walker-maxCount > k){
                map[s.charAt(walker++)]--;
            }
            
            res = Math.max(res, runner-walker);
        }
        return res;
    }
}

類似Longest Substring with At Most Two Distinct Characters.