my ugly c++ solution (16ms) with explanation


  • 0
    S

    The basic idea is as many other people's sliding window. The obsevation is to find the minimum number of transformation needed to transfer a substring

    s[left]s[left+1]s[left+2]...s[right]

    into a series of repeating characters. However, to avoid calculating such minimum number again and again for each window, I maintain a number called "max", which is the frequency of most frequent character in the substring. For example in a string

    SCDCSOS

    max will be 3, which is the frequency of 'S'. The minimum number of transformation will be needed is therefore the sum of all other frequencies, which is in this case 4. When sliding the right end of window, we should update the max possibly, and when moving the left end of window we should be careful to examine the cases of possible changing of max as well, and the most annoying term is when there are multiple characters appearing the most frequently

        int characterReplacement(string s, int k) {
    		int ret = 0;
    		int l = 0;
    		int r = 0;
    
    		int size = s.size();
    		if(size <= k) { return size; }
    
    		vector<int> ch(26, 0);
    
    		int cnt = 0;		// min number of transfer needed to convert s[l...r]  into repeating chars
    		int max = 0;		// the most often characters so far in s[l...r]
    		while(r < size) {
    			if(++ch[s[r]-'A'] > max) {
    				// cnt does not change in this case.
    				max = ch[s[r]-'A'];
    			} else {
    				cnt++;
    				if(cnt > k){
    					// we need to slide the window from left now
    					ret = ret > r-l ? ret : r-l;
    					while(cnt > k) {
    						if(ch[s[l]-'A'] != max) {
    							ch[s[l++]-'A']--;	cnt--;
    						} else {
    							// check how many chars in s[l..r] has frequency =  max
    							int no = 0;
    							for(int i = l; i <= r; i++) {
    								if(ch[s[i]-'A'] == max){
    									no++;
    								}
    							}
    							if(no > 1) {
    								// s[l] is not the only most frequent one, so  cnt decreases
    								cnt--;
    							} 
    							ch[s[l++]-'A']--;
    						}
    					}
    				}
    			}
    			r++;
    			
    		}
    		
    		ret = ret > r-l ? ret : r-l;
    		return ret;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.