Maximum length of identical character substring with m changes
Filed under Amazon
Free read 1 of 3Confirm character set constraints (e.g., uppercase English letters).
The question
Given a string and an integer m denoting allowed character changes, find the maximum length of a substring formed by identical characters after making at most m changes.
Constraints
- 1 <= string length <= 10^5
- 0 <= m <= string length
Examples
- Input
- s = "AABABBA", m = 1
- Output
- 4
- Why
- Replace the middle 'B' with 'A' to get "AAAA" in the substring, giving length 4.
Approach
Confirm character set constraints (e.g., uppercase English letters).
Check every possible substring, count character frequencies, and determine if changes needed <= m. Runs in $O(N^2)$ or $O(N^3)$.
Use a sliding window. Track the count of the most frequent character in the current window. If (window_length - max_count) > m, shrink the window from the left. Runs in $O(N)$ time.
m is larger than the window size, or string has length 1.
Solution
O(N) time, O(1) space
def characterReplacement(s: str, m: int) -> int:
count = {}
res = 0
l = 0
max_f = 0
for r in range(len(s)):
count[s[r]] = 1 + count.get(s[r], 0)
max_f = max(max_f, count[s[r]])
while (r - l + 1) - max_f > m:
count[s[l]] -= 1
l += 1
res = max(res, r - l + 1)
return res
Tips
- What they are testing: Test with m=0, m greater than string length, and strings of all identical characters.
- Common mistake: Recalculating window frequency counts from scratch instead of maintaining a running maximum frequency.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.