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

Topics

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.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sliding Window - The optimal solution uses a variable-size window that expands and contracts based on validity conditions
Hash Map / Frequency Counting - Tracking character frequencies within the current window to determine the most frequent character
Two Pointers - Managing left and right pointers to define and adjust the window boundaries

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

public class Solution {
    public int characterReplacement(String s, int k) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            HashMap<Character, Integer> count = new HashMap<>();
            int maxf = 0;
            for (int j = i; j < s.length(); j++) {
                count.put(s.charAt(j), count.getOrDefault(s.charAt(j), 0) + 1);
                maxf = Math.max(maxf, count.get(s.charAt(j)));
                if ((j - i + 1) - maxf <= k) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    int characterReplacement(string s, int k) {
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            unordered_map<char, int> count;
            int maxf = 0;
            for (int j = i; j < s.size(); j++) {
                count[s[j]]++;
                maxf = max(maxf, count[s[j]]);
                if ((j - i + 1) - maxf <= k) {
                    res = max(res, j - i + 1);
                }
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {number} k
     * @return {number}
     */
    characterReplacement(s, k) {
        let res = 0;
        for (let i = 0; i < s.length; i++) {
            let count = new Map();
            let maxf = 0;
            for (let j = i; j < s.length; j++) {
                count.set(s[j], (count.get(s[j]) || 0) + 1);
                maxf = Math.max(maxf, count.get(s[j]));
                if (j - i + 1 - maxf <= k) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }
}

public class Solution {
    public int CharacterReplacement(string s, int k) {
        int res = 0;
        for (int i = 0; i < s.Length; i++) {
            Dictionary<char, int> count = new Dictionary<char, int>();
            int maxf = 0;
            for (int j = i; j < s.Length; j++) {
                if (count.ContainsKey(s[j])) {
                    count[s[j]]++;
                } else {
                    count[s[j]] = 1;
                }
                maxf = Math.Max(maxf, count[s[j]]);
                if ((j - i + 1) - maxf <= k) {
                    res = Math.Max(res, j - i + 1);
                }
            }
        }
        return res;
    }
}

func characterReplacement(s string, k int) int {
    res := 0
    for i := 0; i < len(s); i++ {
        count := make(map[byte]int)
        maxf := 0
        for j := i; j < len(s); j++ {
            count[s[j]]++
            maxf = max(maxf, count[s[j]])
            if (j - i + 1) - maxf <= k {
                res = max(res, j - i + 1)
            }
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun characterReplacement(s: String, k: Int): Int {
        var res = 0
        for (i in s.indices) {
            val count = HashMap<Char, Int>()
            var maxf = 0
            for (j in i until s.length) {
                count[s[j]] = count.getOrDefault(s[j], 0) + 1
                maxf = maxOf(maxf, count[s[j]]!!)
                if ((j - i + 1) - maxf <= k) {
                    res = maxOf(res, j - i + 1)
                }
            }
        }
        return res
    }
}

class Solution {
    func characterReplacement(_ s: String, _ k: Int) -> Int {
        var res = 0
        let chars = Array(s)

        for i in 0..<chars.count {
            var count = [Character: Int]()
            var maxf = 0

            for j in i..<chars.count {
                count[chars[j], default: 0] += 1
                maxf = max(maxf, count[chars[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

public class Solution {
    public int characterReplacement(String s, int k) {
        int res = 0;
        HashSet<Character> charSet = new HashSet<>();
        for (char c : s.toCharArray()) {
            charSet.add(c);
        }

        for (char c : charSet) {
            int count = 0, l = 0;
            for (int r = 0; r < s.length(); r++) {
                if (s.charAt(r) == c) {
                    count++;
                }

                while ((r - l + 1) - count > k) {
                    if (s.charAt(l) == c) {
                        count--;
                    }
                    l++;
                }

                res = Math.max(res, r - l + 1);
            }
        }
        return res;
    }
}

class Solution {
public:
    int characterReplacement(std::string s, int k) {
        int res = 0;
        unordered_set<char> charSet(s.begin(), s.end());

        for (char c : charSet) {
            int count = 0, l = 0;
            for (int r = 0; r < s.size(); r++) {
                if (s[r] == c) {
                    count++;
                }

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

                res = std::max(res, r - l + 1);
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {number} k
     * @return {number}
     */
    characterReplacement(s, k) {
        let res = 0;
        let charSet = new Set(s);

        for (let c of charSet) {
            let count = 0,
                l = 0;
            for (let r = 0; r < s.length; r++) {
                if (s[r] === c) {
                    count++;
                }

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

                res = Math.max(res, r - l + 1);
            }
        }
        return res;
    }
}

public class Solution {
    public int CharacterReplacement(string s, int k) {
        int res = 0;
        HashSet<char> charSet = new HashSet<char>(s);

        foreach (char c in charSet) {
            int count = 0, l = 0;
            for (int r = 0; r < s.Length; r++) {
                if (s[r] == c) {
                    count++;
                }

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

                res = Math.Max(res, r - l + 1);
            }
        }
        return res;
    }
}

func characterReplacement(s string, k int) int {
    res := 0
    charSet := make(map[byte]bool)

    for i := 0; i < len(s); i++ {
        charSet[s[i]] = true
    }

    for c := range charSet {
        count, l := 0, 0
        for r := 0; r < len(s); r++ {
            if s[r] == c {
                count++
            }

            for (r - l + 1) - count > k {
                if s[l] == c {
                    count--
                }
                l++
            }

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

    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun characterReplacement(s: String, k: Int): Int {
        var res = 0
        val charSet = s.toSet()

        for (c in charSet) {
            var count = 0
            var l = 0
            for (r in s.indices) {
                if (s[r] == c) {
                    count++
                }

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

                res = maxOf(res, r - l + 1)
            }
        }

        return res
    }
}

class Solution {
    func characterReplacement(_ s: String, _ k: Int) -> Int {
        var res = 0
        let charSet = Set(s)
        let chars = Array(s)

        for c in charSet {
            var count = 0, l = 0

            for r in 0..<chars.count {
                if chars[r] == c {
                    count += 1
                }

                while (r - l + 1) - count > k {
                    if chars[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

public class Solution {
    public int characterReplacement(String s, int k) {
        HashMap<Character, Integer> count = new HashMap<>();
        int res = 0;

        int l = 0, maxf = 0;
        for (int r = 0; r < s.length(); r++) {
            count.put(s.charAt(r), count.getOrDefault(s.charAt(r), 0) + 1);
            maxf = Math.max(maxf, count.get(s.charAt(r)));

            while ((r - l + 1) - maxf > k) {
                count.put(s.charAt(l), count.get(s.charAt(l)) - 1);
                l++;
            }
            res = Math.max(res, r - l + 1);
        }

        return res;
    }
}

class Solution {
public:
    int characterReplacement(std::string s, int k) {
        unordered_map<char, int> count;
        int res = 0;

        int l = 0, maxf = 0;
        for (int r = 0; r < s.size(); r++) {
            count[s[r]]++;
            maxf = max(maxf, count[s[r]]);

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

        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {number} k
     * @return {number}
     */
    characterReplacement(s, k) {
        let count = new Map();
        let res = 0;

        let l = 0,
            maxf = 0;
        for (let r = 0; r < s.length; r++) {
            count.set(s[r], (count.get(s[r]) || 0) + 1);
            maxf = Math.max(maxf, count.get(s[r]));

            while (r - l + 1 - maxf > k) {
                count.set(s[l], count.get(s[l]) - 1);
                l++;
            }
            res = Math.max(res, r - l + 1);
        }

        return res;
    }
}

public class Solution {
    public int CharacterReplacement(string s, int k) {
        Dictionary<char, int> count = new Dictionary<char, int>();
        int res = 0;

        int l = 0, maxf = 0;
        for (int r = 0; r < s.Length; r++) {
            if (count.ContainsKey(s[r])) {
                count[s[r]]++;
            } else {
                count[s[r]] = 1;
            }
            maxf = Math.Max(maxf, count[s[r]]);

            while ((r - l + 1) - maxf > k) {
                count[s[l]]--;
                l++;
            }
            res = Math.Max(res, r - l + 1);
        }

        return res;
    }
}

func characterReplacement(s string, k int) int {
    count := make(map[byte]int)
    res, l, maxf := 0, 0, 0

    for r := 0; r < len(s); r++ {
        count[s[r]]++
        if count[s[r]] > maxf {
            maxf = count[s[r]]
        }

        for (r - l + 1) - maxf > k {
            count[s[l]]--
            l++
        }

        if r - l + 1 > res {
            res = r - l + 1
        }
    }

    return res
}

class Solution {
    fun characterReplacement(s: String, k: Int): Int {
        val count = mutableMapOf<Char, Int>()
        var res = 0
        var l = 0
        var maxf = 0

        for (r in s.indices) {
            count[s[r]] = count.getOrDefault(s[r], 0) + 1
            maxf = maxOf(maxf, count[s[r]]!!)

            while (r - l + 1 - maxf > k) {
                count[s[l]] = count[s[l]]!! - 1
                l++
            }

            res = maxOf(res, r - l + 1)
        }

        return res
    }
}

class Solution {
    func characterReplacement(_ s: String, _ k: Int) -> Int {
        var count = [Character: Int]()
        var res = 0
        var l = 0, maxf = 0
        let chars = Array(s)

        for r in 0..<chars.count {
            count[chars[r], default: 0] += 1
            maxf = max(maxf, count[chars[r]]!)

            while (r - l + 1) - maxf > k {
                count[chars[l], default: 0] -= 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.

Common Pitfalls

Not Updating maxf Correctly

The variable maxf tracks the maximum frequency of any character in the current window. A common mistake is recalculating the maximum by iterating through all counts after shrinking the window. In the optimal solution, you do not need to decrease maxf when shrinking because keeping a stale (higher) maxf only makes the window condition stricter, which is still correct. However, misunderstanding this can lead to unnecessary complexity or bugs.

Shrinking the Window Too Aggressively

When the window becomes invalid (window size - maxf > k), you only need to shrink it enough to make it valid again. A common error is resetting the left pointer too far or not updating character counts properly when moving the left pointer. Make sure to decrement the count of s[l] before incrementing l.

Confusing Window Size Calculation

The window size is r - l + 1, not r - l. This off-by-one error is frequent and leads to incorrect validity checks. For example, if l = 0 and r = 2, the window contains 3 characters, not 2. Always double-check your window size formula in the condition (r - l + 1) - maxf <= k.