MediumNeetCode150Hash TableStringSliding Window
Longest Repeating Character Replacement
Find longest substring where you can replace at most k characters to make all same.
Examples
Input
s = "AABABBA", k = 1
Output
4
'AABA' with B->A = 4.
Constraints
- •
1 <= s.length <= 10^5 - •
s consists of uppercase English letters - •
0 <= k <= s.length
Approaches
Try all substrings.
CodeT: O(n^2) | S: O(26)
def characterReplacement(s, k):
mx=0
for i in range(len(s)):
freq={}; maxf=0
for j in range(i,len(s)):
freq[s[j]]=freq.get(s[j],0)+1
maxf=max(maxf,freq[s[j]])
if j-i+1-maxf<=k: mx=max(mx,j-i+1)
return mxTrack max frequency in window.
CodeT: O(n) | S: O(26)
def characterReplacement(s, k):
freq={}; l=0; mx=0; maxf=0
for r in range(len(s)):
freq[s[r]]=freq.get(s[r],0)+1
maxf=max(maxf,freq[s[r]])
if r-l+1-maxf>k:
freq[s[l]]-=1; l+=1
mx=max(mx,r-l+1)
return mxSame approach.
Diagram
Window size - max freq <= k means valid
CodeT: O(n) | S: O(26)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(26) | Try all substrings. |
| Sliding Window | O(n) | O(26) | Track max frequency in window. |
| Sliding Window - Optimized | O(n) | O(26) | Same approach. |
Brute Force
T: O(n^2)S: O(26)
Try all substrings.
Sliding Window
T: O(n)S: O(26)
Track max frequency in window.
Sliding Window - Optimized
T: O(n)S: O(26)
Same approach.
Common Mistakes
Not tracking max frequency correctly
Off-by-one in window size
Not shrinking correctly