using namespace std;
#include <iostream>
#include <string>
#include <unordered_map>
class CharacterReplacement {
public:
static int findLength(const string &str, int k) {
int windowStart = 0, maxLength = 0, maxRepeatLetterCount = 0;
unordered_map<char, int> letterFrequencyMap;
// try to extend the range [windowStart, windowEnd]
for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
char rightChar = str[windowEnd];
letterFrequencyMap[rightChar]++;
maxRepeatLetterCount = max(maxRepeatLetterCount, letterFrequencyMap[rightChar]);
// current window size is from windowStart to windowEnd, overall we have a letter
// which is repeating 'maxRepeatLetterCount' times, this means we can have a window
// which has one letter repeating 'maxRepeatLetterCount' times and the remaining
// letters we should replace. If the remaining letters are more than 'k', it is the
// time to shrink the window as we are not allowed to replace more than 'k' letters
if (windowEnd - windowStart + 1 - maxRepeatLetterCount > k) {
char leftChar = str[windowStart];
letterFrequencyMap[leftChar]--;
windowStart++;
}
maxLength = max(maxLength, windowEnd - windowStart + 1);
cout << "Window End " << windowEnd << " Window Start " << windowStart
<< " maxLength " << maxLength << endl;
}
return maxLength;
}
};
int main(int argc, char *argv[]) {
cout << CharacterReplacement::findLength("aabccbb", 2) << endl;
cout << CharacterReplacement::findLength("abbcb", 1) << endl;
cout << CharacterReplacement::findLength("abccde", 1) << endl;
}
