โ† Amazon questions

Maximum length of identical character substring with m changes

Filed under Amazon

Free read 1 of 3

Confirm 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

  1. Confirm character set constraints (e.g., uppercase English letters).

Solution

O(N) time, O(1) space

Python
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.