Longest Repeating Character Replacement
MediumWindow is valid while (size − maxFreq) ≤ k
Grow a window as long as you can still make it all one letter by changing at most k letters.
The idea
A window can become all one letter if the number of characters to replace — window size minus the most common letter's count — is at most k. Grow while valid, shrink when not.
A
A
B
A
B
B
A
0
1
2
3
4
5
6
k1
Step 1 of 22. Brute force: from each start, extend while at most 1 letters need changing. Values: A, A, B, A, B, B, A. k 1.
1/22
Brute force
timeO(n²)spaceO(1)
Every window.
1for (let i = 0; i < n; i++) {2 const freq = {}; let maxf = 0;3 for (let j = i; j < n; j++) {4 maxf = Math.max(maxf, ++freq[s[j]]);5 if ((j - i + 1) - maxf > k) break;6 best = Math.max(best, j - i + 1);7 }8}Input
- array
- [A, A, B, A, B, B, A]
Memory
- k
- 1
Output
- best
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "ABAB", k = 2
- Output:
- 4
- Explanation:
- Change the 2 Bs (or As) to get AAAA → length 4.
Example 2
- Input:
- s = "AABABBA", k = 1
- Output:
- 4
- Explanation:
- One change yields a run of 4.
Example 3
- Input:
- s = "AAAA", k = 0
- Output:
- 4
- Explanation:
- Already all the same → 4.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.