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

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

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