424.longest repeating character replacement

Description Link to heading

424.longest-repeating-character-replacement

Solution Link to heading

First, note that if the substring can be turned into a substring containing only the same letters by substituing for k times, then there must be max_cnt + k >= subarray.size(); then the substring that does not satisfy the condition must have max_cnt + k < subarray.size(), and according to this, we can use the sliding window method;

If it satifies the condition, just right++, else right++, left++, so right - left must be incremental. And all kind of character will be checked.

Code Link to heading

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> num(26);
        int n = s.length();
        int maxn = 0;
        int left = 0, right = 0;
        while (right < n) {
            num[s[right] - 'A']++;
            maxn = max(maxn, num[s[right] - 'A']);
            if (right - left + 1 - maxn > k) {
                num[s[left] - 'A']--;
                left++;
            }
            right++;
        }
        return right - left;
    }
};