Practice › Sliding Window
Longest Repeating Character Replacement
Medium · Sliding Window · Asked at Google, Amazon, Microsoft, Uber
You may change at most k characters of the string to any other uppercase letter. Print the length of the longest substring containing a single repeated letter that you can obtain.
Input
First line: s (uppercase letters). Second line: k.
Output
The maximum length.
Constraints
- 1 ≤ |s| ≤ 10^5
- 0 ≤ k ≤ |s|
A window is valid if (window length − count of its most frequent letter) ≤ k.
Example 1
Input
ABAB 2
Output
4
Example 2
Input
AABABBA 1
Output
4
Hints
- In a window, keep the most frequent letter and replace all the others. That costs (length − maxCount) changes.
- Grow the window; if the cost exceeds k, move the left end one step. maxCount never needs to decrease — a smaller value can never give a longer answer.
Approach
Count letters inside the window and track maxCount, the highest count seen. When (r − l + 1) − maxCount > k, slide the left end by one (the window never shrinks below the best length found so far). Not lowering maxCount is safe: the answer only improves when a window with a larger maxCount appears, so the final window length is the answer.
Complexity: O(n) time · O(26) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
int k;
cin >> s >> k;
int cnt[26] = {0}, l = 0, mx = 0, best = 0;
for (int r = 0; r < (int)s.size(); r++) {
mx = max(mx, ++cnt[s[r] - 'A']);
if (r - l + 1 - mx > k) cnt[s[l++] - 'A']--;
best = max(best, r - l + 1);
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = sys.stdin.read().split()
s, k = data[0], int(data[1])
cnt = [0] * 26
l = mx = best = 0
for r, c in enumerate(s):
cnt[ord(c) - 65] += 1
mx = max(mx, cnt[ord(c) - 65])
if r - l + 1 - mx > k:
cnt[ord(s[l]) - 65] -= 1
l += 1
best = max(best, r - l + 1)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int k = sc.nextInt();
int[] cnt = new int[26];
int l = 0, mx = 0, best = 0;
for (int r = 0; r < s.length(); r++) {
mx = Math.max(mx, ++cnt[s.charAt(r) - 'A']);
if (r - l + 1 - mx > k) cnt[s.charAt(l++) - 'A']--;
best = Math.max(best, r - l + 1);
}
System.out.println(best);
}
}Solve Longest Repeating Character Replacement online · All practice problems