424. Longest Repeating Character Replacement - Explanation

Description

You are given a string s consisting of only uppercase english characters and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English character.

After performing at most k replacements, return the length of the longest substring which contains only one distinct character.

Example 1:

Input: s = "XYYX", k = 2

Output: 4

Explanation: Either replace the 'X's with 'Y's, or replace the 'Y's with 'X's.

Example 2:

Input: s = "AAABABB", k = 1

Output: 5

Constraints:

1 <= s.length <= 1000
0 <= k <= s.length

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(m) space, where n is the length of the given string and m is the number of unique characters in the string.

Hint 1

Which characters would you replace in a string to make all its characters identical? Can you think with respect to the frequency of the characters?

Hint 2

It is always optimal to replace characters with the most frequent character in the string. Why? Because using the most frequent character minimizes the number of replacements required to make all characters in the string identical. How can you find the number of replacements now?

Hint 3

The number of replacements is equal to the difference between the length of the string and the frequency of the most frequent character in the string. A brute force solution would be to consider all substrings, use a hash map for frequency counting, and return the maximum length of the substring that has at most k replacements. This would be an O(n^2) solution. Can you think of a better way?

Hint 4

We can use the sliding window approach. The window size will be dynamic, and we will shrink the window when the number of replacements exceeds k. The result will be the maximum window size observed at each iteration.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The brute-force idea is to try every possible substring starting at every index.
For each start point, we expand the substring and keep track of how many times each character appears.
A substring is valid if we can make all its characters the same by replacing at most k of them.
To check this, we track the most frequent character inside the substring — everything else would need to be replaced.
If the number of replacements needed is within k, we update the answer.
This works but is slow because it checks many overlapping substrings.

Algorithm

Initialize res = 0 to store the longest valid window.
For each starting index i:
- Create an empty frequency map and set maxf = 0.
- Extend the substring by increasing j from i to the end:
  - Update the frequency of s[j].
  - Update maxf (most frequent character in the current window).
  - If the window size minus maxf is <= k, it is valid.
    - Update res with the window size.
Return res after testing all starting positions.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        res = 0
        for i in range(len(s)):
            count, maxf = {}, 0
            for j in range(i, len(s)):
                count[s[j]] = 1 + count.get(s[j], 0)
                maxf = max(maxf, count[s[j]])
                if (j - i + 1) - maxf <= k:
                    res = max(res, j - i + 1)
        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(m)$

Where $n$ is the length of the string and $m$ is the total number of unique characters in the string.

2. Sliding Window

Intuition

We try to make a valid window where all characters become the same, but instead of checking every substring, we fix a target character c and ask:

“How long can the window be if we want the entire window to become c using at most k replacements?”

We slide a window across the string and count how many characters inside it already match c.
If the number of characters that don’t match c is more than k, the window is invalid, so we shrink it from the left.
By doing this for every possible character, we find the longest valid window.

This idea is simple and beginner-friendly because we only track:

how many characters match c
how many replacements are needed

Algorithm

Put all unique characters of the string into a set charSet.
For each character c in charSet:
- Set l = 0 and count = 0 (count of c inside the window).
- Slide the right pointer r across the string:
  - Increase count when s[r] == c.
  - If the window needs more than k replacements, move l forward and adjust count.
  - Update res with the current valid window size.
Return the maximum window size found.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        res = 0
        charSet = set(s)

        for c in charSet:
            count = l = 0
            for r in range(len(s)):
                if s[r] == c:
                    count += 1

                while (r - l + 1) - count > k:
                    if s[l] == c:
                        count -= 1
                    l += 1

                res = max(res, r - l + 1)
        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m)$

Where $n$ is the length of the string and $m$ is the total number of unique characters in the string.

3. Sliding Window (Optimal)

Intuition

We want the longest window where we can make all characters the same using at most k replacements.
The key insight is that the window is valid as long as:

window size – count of the most frequent character ≤ k

Why?
Because the characters that aren’t the most frequent are the ones we would need to replace.

So while expanding the window, we track:

the frequency of each character,
the most frequent character inside the window (maxf).

If the window becomes invalid, we shrink it from the left.
This gives us one clean sliding window pass.

Algorithm

Create a frequency map count and initialize l = 0, maxf = 0, and res = 0.
Move the right pointer r across the string:
- Update the frequency of s[r].
- Update maxf with the highest frequency seen so far.
If the window is invalid (window size - maxf > k):
- Shrink the window from the left and adjust counts.
Update the result with the valid window size.
Return res at the end.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        res = 0

        l = 0
        maxf = 0
        for r in range(len(s)):
            count[s[r]] = 1 + count.get(s[r], 0)
            maxf = max(maxf, count[s[r]])

            while (r - l + 1) - maxf > k:
                count[s[l]] -= 1
                l += 1
            res = max(res, r - l + 1)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(m)$

Where $n$ is the length of the string and $m$ is the total number of unique characters in the string.