How do you approach Longest Repeating Character Replacement?

A window is fixable with k replacements when (window length - count of its most frequent letter) <= k.

What is the time complexity of Longest Repeating Character Replacement?

Time complexity: O(n) - each index enters and leaves the window once. Space complexity: O(26) = O(1) - the frequency table.

What are common mistakes on Longest Repeating Character Replacement?

Shrinking with if instead of while - one removal is often not enough to restore the invariant. Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove. Never recording the answer for a window that ends at the last index.

gitGood.dev

← Back to problems

Longest Repeating Character Replacement

MediumAlgorithms

Description

You are given a string s of uppercase English letters and an integer k. You can choose any character of the string and change it to any other uppercase English letter. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1

Input: s = "ABAB", k = 2

Output: 4

Explanation: Replace the two 'A's with two 'B's or vice versa to get "BBBB" or "AAAA".

Example 2

Input: s = "AABABBA", k = 1

Output: 4

Explanation: Replace the one 'A' in the middle with 'B' to form "AABBBBA". The substring "BBBB" has length 4.

Example 3

Input: s = "ABCDE", k = 1

Output: 2

Explanation: With one replacement, the best you can do is a window of 2 (one kept letter plus one replaced).

Constraints

- 1 <= s.length <= 10^5 - s consists of only uppercase English letters. - 0 <= k <= s.length

Longest Repeating Character Replacement: approach, complexity and pitfalls

A medium sliding window problem, graded against 7 test cases (4 of them hidden).

The pattern: Sliding Window

A moving window over a contiguous run, expanding and contracting to hold an invariant.

Reach for it when you see: "Longest/shortest contiguous subarray or substring satisfying X."

If you are stuck

Show the 3-step hint ladder

A window is fixable with k replacements when (window length - count of its most frequent letter) <= k.
Grow a sliding window to the right, tracking letter frequencies and the highest frequency seen in the window.
When the window becomes invalid, shrink it from the left. The max frequency never needs to decrease - a stale value only makes the check conservative, never wrong.

The optimal approach

Show the approach: Sliding Window with Max Frequency

Maintain a window `[left, right]` and a count of each letter inside it. The window is valid when `windowLength - maxFrequency <= k` (every non-majority character can be replaced). Expand `right` each step; if the window becomes invalid, move `left` forward once.

The subtle trick: `maxFrequency` is never decremented when the window shrinks. A stale (too-high) value can only keep the window from growing, never produce a wrong answer - the answer only improves when a genuinely higher frequency is found.

Time: O(n) - each index enters and leaves the window once
Space: O(26) = O(1) - the frequency table

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Sliding Window mistakes

These apply to the pattern as a whole, not just this problem.

Shrinking with `if` instead of `while` - one removal is often not enough to restore the invariant.
Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove.
Never recording the answer for a window that ends at the last index.

← Back to problems

Longest Repeating Character Replacement

MediumAlgorithms

Description

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1

Input: s = "ABAB", k = 2

Output: 4

Explanation: Replace the two 'A's with two 'B's or vice versa to get "BBBB" or "AAAA".

Example 2

Input: s = "AABABBA", k = 1

Output: 4

Explanation: Replace the one 'A' in the middle with 'B' to form "AABBBBA". The substring "BBBB" has length 4.

Example 3

Input: s = "ABCDE", k = 1

Output: 2

Explanation: With one replacement, the best you can do is a window of 2 (one kept letter plus one replaced).

Constraints

- 1 <= s.length <= 10^5 - s consists of only uppercase English letters. - 0 <= k <= s.length

Longest Repeating Character Replacement: approach, complexity and pitfalls

A medium sliding window problem, graded against 7 test cases (4 of them hidden).

The pattern: Sliding Window

A moving window over a contiguous run, expanding and contracting to hold an invariant.

Reach for it when you see: "Longest/shortest contiguous subarray or substring satisfying X."

If you are stuck

Show the 3-step hint ladder

A window is fixable with k replacements when (window length - count of its most frequent letter) <= k.
Grow a sliding window to the right, tracking letter frequencies and the highest frequency seen in the window.
When the window becomes invalid, shrink it from the left. The max frequency never needs to decrease - a stale value only makes the check conservative, never wrong.

The optimal approach

Show the approach: Sliding Window with Max Frequency

Time: O(n) - each index enters and leaves the window once
Space: O(26) = O(1) - the frequency table

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Sliding Window mistakes

These apply to the pattern as a whole, not just this problem.

Shrinking with `if` instead of `while` - one removal is often not enough to restore the invariant.
Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove.
Never recording the answer for a window that ends at the last index.