424. Longest Repeating Character Replacement -----------M ~~~!!!!!!!

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. 

A:

就是很直观的的DP啊。  

思路就是：每次在一个位置，往前变的是多少。

class Solution {
public:
    int characterReplacement(string s, int k) {
        // DP wrt k
        int n = s.length();
        vector<vector<int>> V(k+1,vector<int>(n,1));// at V[i][j], with at most i operation, eding at j_th position, how many we can get
        for(int j=1; j<n; j++){
            V[0][j] = s[j] == s[j-1]? V[0][j-1]+1:1;
        }
        for(int i = 1;i<=k; i++){
            for(int j = 1;j<n;j++){
                int preIndex = j - V[i-1][j];
                V[i][j] = V[i-1][j];
                if(preIndex>=0){ // do operation at preIndex.
                    preIndex--;
                    V[i][j]++;
                }
                while(preIndex>=0 && s[preIndex] == s[j]){
                    ++V[i][j];
                    --preIndex;
                }
            }
        }
        int res = 0;
        for(int j = 0;j<n;j++){
            res = max(res, V[k][j]);
        }
        return res;
    }
};

然而，上面的思路是错误的。 我们错误的假设了，  每一次，最后一个字母不变。然而是不对的

可行的更改是：每个endposition，都有个possible char的值。 然而这样还是不行的。 有可能AAAAABB   k==2 

直接看答案吧：

Maintain a window that slides down the string. 

In each iteration, we move the "end" of the window down one step. 

Use a vector to record the number of every letter within the window, and maintain the number of the most letter in the window. 

The window length minus the number of the most letter is the minimum number of operations we need to convert all the letters in the window to the same letter. 

Therefore, when the minimum number of operations surpasses "k", we need to shrink the window by moving the "start" of the window down one step. 

Now the window length is the length of the substring composed of the same letter that we can get. 

Slide the window all the way down the whole string and record the maximum window length during the process.

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> Count(26,0);
        int res = 0, startIndex = 0;
        int maxCharCount = 0;
        for(int i =0;i<s.length();i++){
            Count[s[i]-'A']++;
            maxCharCount = max(maxCharCount, Count[s[i]-'A']); // only newly added matter
            if(i-startIndex+1 - maxCharCount> k){// s[startIndex] != s[i]  for sure
                char toBeDeleteChar = s[startIndex++];
                Count[toBeDeleteChar-'A']--;
            }
            res = max(res, i - startIndex + 1);
        }
        return res;
    }
};