424. The longest repeated character after replacement ●●

424. The longest repeated character after replacement ●●

describe

Give you a string s And an integer k . You can select any character in the string , And change it to any other Capitalization English characters . This operation can be performed up to k Time .

After doing this , return The length of the longest substring containing the same letter .

Example

Input ：s = “AABABBA”, k = 1
Output ：4
explain ：
Will the middle one ’A’ Replace with ’B’, The string changes to “AABBBBA”.
Substring “BBBB” There is the longest repeating letter , The answer for 4.

Answer key

1. Double pointer 1

Use a one-dimensional array to store the occurrence times of each letter in the window , Each time, the letters on the left border are used as fixed letters （ That is, replace different letters with this letter ）, The right pointer moves to the right one by one , When it can no longer be replaced , Move the left pointer to the right , And update the current fixed letter ;

Be careful , Because this solution takes the left boundary letter as the fixed letter every time , So we also need to consider the length of the letter before the left boundary after it is replaced ,

such as s = “ACBBB”,k = 2; The correct result is 5; If you don't consider front , The result is 3.

class Solution {
    
public:
    int characterReplacement(string s, int k) {
    
        vector<int> cnts(26, 0);
        int n = s.length(), ans = 0;
        int l = 0, rest = k;
        cnts[s[0]-'A'] = 1;				//  Initial left border 
        for(int r = 1; r < n; ++r){
    
            if(s[r] != s[l]) --rest;	//  Replace operation ,--rest
            ++cnts[s[r]-'A'];			//  Statistics frequency 
            while(rest < 0){
    			//  Replacement failed 
                --cnts[s[l]-'A'];		
                ++l;					//  Move the left pointer 
                rest = k - ((r-l+1) - cnts[s[l]-'A']));	//  Update the fixed letter to the left border letter ,(r-l+1)-cnts[s[l]-'A']  Indicates the number of letters to be replaced in the current window 
            }
            int front = min(rest, l);		//  Consider replacing the previous letter 
            ans = max(ans, r-l+1+front);	//  Update Max 
        }
        return ans;
    }
};

2. Double pointer 2

Enumerate each position in the string as the right endpoint , Then find the location of its farthest left endpoint , Satisfy the interval except The type of characters that appear most often outside , The remaining characters （ That is, non longest repeating character ） No more than k individual .

So we can think of using double pointers to maintain these intervals , Every time the right pointer moves right , If the interval still satisfies the condition , So the left pointer doesn't move , Otherwise, the left pointer can be moved one space to the right at most , Guarantee The interval length does not decrease （ Remain unchanged or increase ）.

Although such operation will cause some intervals not to meet the conditions , That is, after moving the left pointer , The non longest repeating character in this interval exceeds k individual （maxSame Changed but may not be updated ）.
But such a range is also unlikely to contribute to the answer （ Until you move the right pointer to a letter that appears more frequently ）. When we move the right pointer to the end , The length of the interval corresponding to the left and right pointers must correspond to the interval with the largest length .

Every time the interval moves right , We update the number of times the character shifted right appears , Then try to use it to update the historical maximum number of repeated characters , Finally, we use the maximum to calculate the number of non longest repeating characters in the interval , In order to judge whether the left pointer needs to move right .

class Solution {
    
public:
    int characterReplacement(string s, int k) {
    
        vector<int> cnts(26, 0);
        int n = s.length();
        int l = 0, r = 0, maxSame = 0;
        for(; r < n; ++r){
    
            ++cnts[s[r]-'A'];
            maxSame = max(maxSame, cnts[s[r]-'A']);	//  Maximum update frequency , Only when it occurs more frequently 
            if(k < (r-l+1) - maxSame){
    		        //  Replacement failed 
                --cnts[s[l]-'A'];			        //  Move the left pointer , contract the window （ The maximum total length does not change at this time ）
                ++l;
            }
        }                                           // for  In circulation  r  Take one more step , At the end  r = n
        return r-l;							        //  The window size is guaranteed not to decrease , The maximum eligible window length 
    }
};