424.longest-repeating-character-replacement 替换后的最长重复字符

问题描述

424.替换后的最长重复字符

解题思路

首先，注意一点，子串如果能通过k次替换变成只包含相同字母的子串，那么一定有max_cnt + k >= subarray.size();那么不满足条件的子串一定有max_cnt + k < subarray.size()，根据这一点，我们可以采用滑动窗口法;

如果满足条件，那么只增加right，如果不满足条件，right++、left++，这样right - left一定是递增的，并且会遍历搜寻到所有的不同字符。

代码

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;
    }
};