# 424 - Longest Repeating Character Replacement

## 解法一 - Sliding Window

``````It is tricky to use the sliding window.
The tricky point is if(max + k <= end - start) where max doesn't change, if you decrease count by count[s.charAt(start++)]--.
If the start pointer originally points to maxCount character, max should be decreased as well, but it didn't.
I hope my example can make it clear.

Let's say we have AABCDAAA, k = 2.
When start points to A, the if(max + k <= end - start) will be met after end moves to D.
So, Count[A] decreases by 1 and start++.
(Max + k) are still same.

next, by intuition, max should be 1. Here it actually doesn't matter!
As we move on, A stills doesn't qualify, but count[A]++.
Shift window right and we deceases Count[A] = 1.
MaxCount = 2 still seems to make no sense now.
So, we shift window towards right.

Next, A makes Count[A] increased to 2, and maxCount doesn't change.
Then, shift to right, start = C.
Now substring is CDAA. Last, count[A]++ and becomes 3.
That's when maxCount is reached and changed.
At this point, we found a larger window!
So it doesn't matter if maxCount is incorrect in the process. Because, we only care about if we get the largest window.

maxCount is actually larger than actual count because it represents current global maxWindow.
It means there was a max substring before.
``````
``````class Solution {
public:
int characterReplacement(string s, int k) {
int maxLen = 0;
unordered_map<char, int> table;

int windowStart = 0, maxRepeatingLen = 0;
for(int windowEnd=0; windowEnd<s.length(); windowEnd++) {
table[s[windowEnd]]++;
maxRepeatingLen = max(maxRepeatingLen, table[s[windowEnd]]);

while(windowEnd-windowStart+1-maxRepeatingLen > k) {
table[s[windowStart]]--;
windowStart++;
}

maxLen = max(maxLen, windowEnd-windowStart+1);
}

return maxLen;
}
};
``````

## 延伸題 - Longest Subarray with Ones after Replacement

``````using namespace std;

#include <iostream>
#include <vector>

class ReplacingOnes {
public:
static int findLength(const vector<int>& arr, int k) {
int maxLen = 0;
int windowStart = 0, maxOneCount = 0;

for(int windowEnd=0; windowEnd<arr.size(); windowEnd++) {
if(arr[windowEnd] == 1) maxOneCount++;

while(windowEnd-windowStart+1-maxOneCount > k) {
if(arr[windowStart] == 1) {
maxOneCount--;
}
windowStart++;
}

maxLen = max(maxLen, windowEnd-windowStart+1);
}

return maxLen;
}
};
``````