424. Longest Repeating Character Replacement

https://leetcode.com/problems/longest-repeating-character-replacement/

Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string.

In one operation, you can choose any character of the string and change it to any other uppercase English character.

Find the length of the longest sub-string 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 = 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.

Thoughts

数组元素由[A, Z]组成，问能把其中k个字符全替换成任一字符后最长的重复子串长度。argmax + substring => dynamic window 或DP。遍历并以当前字符s[r]为底，当窗口内出现最多的子符对应的次数mx加上允许替换的字母数k 超过窗口宽度时说明窗口可以全部填满成窗口该字符，即mx + k > r - l + 1时，窗口还可以更长；mx + k < r - l + 1时说明能构成的最长的重复字母长度不足以覆盖整个窗口，因为多了一位s[r]，左边压缩一位。分析当r右移时，l是否会回弹，两种情况：1. s[r] == 最多频率的字符，l往左移保证(mx + 1) + k < r - (l - 1) + 1 == mx + k < r - l + 1，不能覆盖；2. s[r]不为最多频率的字符，mx + (k + 1) < r - (l - 1) + 1，不能覆盖。因此满足动态窗口题解所须『压缩后不回弹』条件。

Code

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        l, freq, res = 0, [0] * 26, 0
        for r, c in enumerate(s):
            freq[ord(c) - ord('A')] += 1
            if r - l + 1 > max(freq) + k: 
                freq[ord(s[l]) - ord('A')] -= 1  
                l += 1 
            res = max(res, r - l + 1)
        return res
            

class Solution {
    public int characterReplacement(String s, int k) {
        if (s.length() == 0) {
            return 0;
        }
        int[] amount = new int[26];
        int l = 0, r = 0, res = 0;      

        while (r < s.length()) {
            amount[s.charAt(r) - 'A']++;
            int maxCount = 0;
            for (int i = 0; i < 26; i ++) {
                maxCount = Math.max(maxCount, amount[i]);
            }

            if (maxCount + k < r - l + 1) {
                // Do not extend the window size.
                // Move the whole window to the right
                amount[s.charAt(l) - 'A']--;
                l++;
            }

            res = Math.max(res, r - l + 1);
            r++;
        }

        return res;
    }
}

Analysis

时间复杂度O(n), 空间O(1).