Character replacement: definition
Find the longest contiguous part of a string that can become one repeated letter using a limited number of replacements. This is a variable-size sliding-window problem.
Task example: Longest Repeating Character Replacement
Given uppercase English letters s and a budget k, return the longest substring length that can be made uniform by changing at most k letters. Keep the order and return a length, not a modified string.
In AABA, keep the three A letters and replace B. Four minus three is one change. The input itself stays unchanged.
Brute force: video explanation
s = "AABABBA", k = 1 → 4
Prefer reading? Follow the steps below.
- Choose left and clear counts. Extend right, counting each letter and tracking the largest frequency most.
- The changes needed are length - most. If this exceeds k, stop this start: extending it cannot reduce that number.
- For every valid window, update best. Restart from each index and return the largest length. AABA needs one change and gives length 4.
Time complexity · O(n²)
There are n starts, each with up to n extensions: O(n²) time in the worst case.
Space complexity · O(1)
The table stores at most 26 uppercase English letters. With this fixed alphabet, extra space is O(1). For an alphabet of size A, it is O(min(n, A)).
Sliding window: video explanation
s = "AABABBA", k = 1 → 4
Prefer reading? Follow the steps below.
- Add s[right] to counts. Compute the current largest frequency with max(counts.values()).
- While window length minus that frequency exceeds k, subtract s[left] from counts and advance left. Recompute the maximum after every removal.
- Update best only after the window fits the budget. At index 4, AABAB needs two changes, so remove two left A letters to reach the valid window BAB. Best stays 4.
Reusing counts avoids repeated scans. Once a start is invalid, extending it cannot make it valid, so discarding it is safe. This version always uses the exact current maximum, not a stale historical value.
Time complexity · O(n)
Each pointer moves forward at most n times. Finding the maximum scans at most 26 counts, so time is O(26n) = O(n). For a variable alphabet of size A, this implementation takes O(nA).
Space complexity · O(1)
The table stores at most 26 uppercase English letters. With this fixed alphabet, extra space is O(1). For an alphabet of size A, it is O(min(n, A)).