Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Longest Repeating Character Replacement

LeetCode #424Medium
Variable window · invariant len − maxFreq ≤ k

Given a string and a budget of k character changes, find the length of the longest substring made of a single repeated character after performing at most k replacements.

Asked atAmazonGoogle
step 1 / 55
A
A
B
A
B
B
A
[0][1][2][3][4][5][6]
Brute force · extend from every start
▸
1given s, k
2best ← 0
3for i ← 0 to n − 1:
4    freq ← {}; maxFreq ← 0
5    for j ← i to n − 1:
6        count s[j]; if len − maxFreq ≤ k:
7            best = max(best, len)
8        else: break
9return best
state
  • s"AABABBA"
  • k1

line 1You may replace at most k = 1 characters. Find the longest window you could turn into ONE repeated letter. A window of length L works iff L − (count of its most frequent letter) ≤ k.