The challenge
Return the longest substring length that can become a single repeated letter after replacing at most k characters.
Uppercase English letters; k ≥ 0. Empty input returns 0.
Example
AABABBA, k = 1 → 4: replace the B in AABA to get AAAA.
Use the walkthrough below to inspect the input and each state change.
See Character replacement, step by step
Expand, shrink, and inspect the window state.
7 elements · zero-based indicesk = 1
Current windowRecorded answerOutside window
- Left
- 0
- Right
- -1
- Length
- 0
Step 01 / 20
Start with an empty window
Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.
left = 0; right = −1Answer so far
0
View exact input
Input: ["A","A","B","A","B","B","A"] · k = 1
Current window is empty.
Put it into code
Keep the most common letter and replace the rest. This version recomputes the exact maximum frequency so every displayed window is truly valid.
Indices are zero-based. C++ uses C++17 or later.
def character_replacement(s, k):
# Uppercase English letters. Recompute the exact max count.
count = [0] * 26
left = best = 0
for right, char in enumerate(s):
count[ord(char) - ord('A')] += 1
while right - left + 1 - max(count) > k:
count[ord(s[left]) - ord('A')] -= 1
left += 1
best = max(best, right - left + 1)
return best#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
int character_replacement(const string& s, int k) {
array<int, 26> count{};
int left = 0, best = 0;
for (int r = 0; r < (int)s.size(); ++r) {
++count[s[r] - 'A'];
while (r - left + 1 - *max_element(count.begin(), count.end()) > k)
--count[s[left++] - 'A'];
best = max(best, r - left + 1);
}
return best;
}