Longest Repeating Character Replacement (LC 424): Sliding Window

Find the longest substring you can turn into one repeated letter with at most k replacements. Solve LeetCode 424 with a sliding window that tracks the most frequent letter, in O(n) time and O(1) space.

Language Selection

Choose your preferred programming language

Showing: Python

Longest Repeating Character Replacement

Problem Statement

You are given a string s of uppercase English letters and an integer k. You may pick any character of the string and change it to any other uppercase letter, and you can do this at most k times in total.

Return the length of the longest substring that can be made to consist of a single repeated letter after your changes.

Examples

Example 1:

Input: s = "AABCBBA", k = 1
Output: 4
Explanation: Take the substring "BCBB" and change the C to B, giving "BBBB".
No substring of length 5 can be made uniform with one change.

Example 2:

Input: s = "XYXXZX", k = 2
Output: 6
Explanation: Change Y and Z to X. The whole string becomes "XXXXXX".

Example 3:

Input: s = "ABCD", k = 0
Output: 1
Explanation: No changes are allowed and no two neighbors match,
so the best is any single letter.

Constraints

  • 1 <= s.length <= 10^5
  • s contains only uppercase English letters
  • 0 <= k <= s.length

Approach 1: Expand from Every Start

Algorithm

A substring can be made uniform with at most k changes exactly when

length - (count of its most frequent letter) <= k,

because the cheapest plan keeps the most common letter and rewrites everything else.

For each starting index, grow the substring one character at a time while keeping letter counts and the running maximum count. Once a window needs more than k changes, extending it further never helps: each extra character adds 1 to the length but at most 1 to the top count, so the number of changes needed never goes down. You can stop and move to the next start.

  1. For each start, reset 26 counters and maxCount = 0.
  2. For each end >= start, add s[end], update maxCount.
  3. If (end - start + 1) - maxCount <= k, update the best length; otherwise break.
  4. Return the best length.

Implementation

Python:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        n = len(s)
        best = 0
        for start in range(n):
            counts = [0] * 26
            max_count = 0
            for end in range(start, n):
                idx = ord(s[end]) - ord('A')
                counts[idx] += 1
                max_count = max(max_count, counts[idx])
                # changes needed = letters that are not the majority letter
                if (end - start + 1) - max_count > k:
                    break           # longer windows from this start need even more
                best = max(best, end - start + 1)
        return best

Java:

class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length(), best = 0;
        for (int start = 0; start < n; start++) {
            int[] counts = new int[26];
            int maxCount = 0;
            for (int end = start; end < n; end++) {
                maxCount = Math.max(maxCount, ++counts[s.charAt(end) - 'A']);
                // changes needed = letters that are not the majority letter
                if (end - start + 1 - maxCount > k) break;
                best = Math.max(best, end - start + 1);
            }
        }
        return best;
    }
}

Go:

func characterReplacement(s string, k int) int {
    n, best := len(s), 0
    for start := 0; start < n; start++ {
        var counts [26]int
        maxCount := 0
        for end := start; end < n; end++ {
            counts[s[end]-'A']++
            maxCount = max(maxCount, counts[s[end]-'A'])
            // changes needed = letters that are not the majority letter
            if end-start+1-maxCount > k {
                break // longer windows from this start need even more
            }
            best = max(best, end-start+1)
        }
    }
    return best
}

JavaScript:

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function (s, k) {
    const n = s.length;
    let best = 0;
    for (let start = 0; start < n; start++) {
        const counts = new Array(26).fill(0);
        let maxCount = 0;
        for (let end = start; end < n; end++) {
            const idx = s.charCodeAt(end) - 65; // 'A' is 65
            maxCount = Math.max(maxCount, ++counts[idx]);
            // changes needed = letters that are not the majority letter
            if (end - start + 1 - maxCount > k) break;
            best = Math.max(best, end - start + 1);
        }
    }
    return best;
};

C#:

using System;

public class Solution {
    public int CharacterReplacement(string s, int k) {
        int n = s.Length, best = 0;
        for (int start = 0; start < n; start++) {
            var counts = new int[26];
            int maxCount = 0;
            for (int end = start; end < n; end++) {
                maxCount = Math.Max(maxCount, ++counts[s[end] - 'A']);
                // changes needed = letters that are not the majority letter
                if (end - start + 1 - maxCount > k) break;
                best = Math.Max(best, end - start + 1);
            }
        }
        return best;
    }
}

C++:

#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.size(), best = 0;
        for (int start = 0; start < n; start++) {
            int counts[26] = {0};
            int maxCount = 0;
            for (int end = start; end < n; end++) {
                maxCount = max(maxCount, ++counts[s[end] - 'A']);
                // changes needed = letters that are not the majority letter
                if (end - start + 1 - maxCount > k) break;
                best = max(best, end - start + 1);
            }
        }
        return best;
    }
};

Complexity Analysis

  • Time: O(n^2) in the worst case, for example when k is large and every start can extend to the end of the string.
  • Space: O(1). The counter array always has 26 entries.

Approach 2: Sliding Window with Max Frequency (Optimal)

Algorithm

Keep one window [left, right] that moves across the string, along with letter counts for the window and maxCount, the highest count any letter has reached.

  1. Move right forward one step at a time, adding s[right] to the counts and updating maxCount.
  2. If the window is invalid, that is (right - left + 1) - maxCount > k, move left forward by one and remove s[left] from the counts.
  3. Record right - left + 1 as a candidate answer.

Two details make this O(n):

  • The window never shrinks. Each step adds one character on the right and removes at most one on the left, so the window length never decreases. That is fine because we only care about the longest valid window, and a shorter one could never improve the answer.
  • maxCount is never decreased, even when the letter that set it leaves the window. A stale, too-high maxCount can only let the current window keep its length. It never lets the window grow. Once the window has become invalid at least once, it can grow again only when the newly added letter pushes maxCount to a new high, and at that moment the window genuinely contains maxCount copies of that letter, so length - maxCount <= k really holds. Before the first invalid step the window is valid by definition (for example "ABCD" with k = 3 grows to 4 while maxCount stays 1). So every time the answer increases, it is backed by a real valid window.

Implementation

Python:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = [0] * 26
        left = 0
        max_count = 0      # highest count any letter has reached in a window
        best = 0
        for right, ch in enumerate(s):
            idx = ord(ch) - ord('A')
            counts[idx] += 1
            max_count = max(max_count, counts[idx])
            # too many changes needed: slide the window right by one
            if (right - left + 1) - max_count > k:
                counts[ord(s[left]) - ord('A')] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

Java:

class Solution {
    public int characterReplacement(String s, int k) {
        int[] counts = new int[26];
        int left = 0, maxCount = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            // maxCount only ever grows; see the explanation above
            maxCount = Math.max(maxCount, ++counts[s.charAt(right) - 'A']);
            // too many changes needed: slide the window right by one
            if (right - left + 1 - maxCount > k) {
                counts[s.charAt(left) - 'A']--;
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Go:

func characterReplacement(s string, k int) int {
    var counts [26]int
    left, maxCount, best := 0, 0, 0
    for right := 0; right < len(s); right++ {
        counts[s[right]-'A']++
        // maxCount only ever grows; see the explanation above
        maxCount = max(maxCount, counts[s[right]-'A'])
        // too many changes needed: slide the window right by one
        if right-left+1-maxCount > k {
            counts[s[left]-'A']--
            left++
        }
        best = max(best, right-left+1)
    }
    return best
}

JavaScript:

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function (s, k) {
    const counts = new Array(26).fill(0);
    let left = 0, maxCount = 0, best = 0;
    for (let right = 0; right < s.length; right++) {
        // maxCount only ever grows; see the explanation above
        maxCount = Math.max(maxCount, ++counts[s.charCodeAt(right) - 65]);
        // too many changes needed: slide the window right by one
        if (right - left + 1 - maxCount > k) {
            counts[s.charCodeAt(left) - 65]--;
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
};

C#:

using System;

public class Solution {
    public int CharacterReplacement(string s, int k) {
        var counts = new int[26];
        int left = 0, maxCount = 0, best = 0;
        for (int right = 0; right < s.Length; right++) {
            // maxCount only ever grows; see the explanation above
            maxCount = Math.Max(maxCount, ++counts[s[right] - 'A']);
            // too many changes needed: slide the window right by one
            if (right - left + 1 - maxCount > k) {
                counts[s[left] - 'A']--;
                left++;
            }
            best = Math.Max(best, right - left + 1);
        }
        return best;
    }
}

C++:

#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
    int characterReplacement(string s, int k) {
        int counts[26] = {0};
        int left = 0, maxCount = 0, best = 0;
        for (int right = 0; right < (int)s.size(); right++) {
            // maxCount only ever grows; see the explanation above
            maxCount = max(maxCount, ++counts[s[right] - 'A']);
            // too many changes needed: slide the window right by one
            if (right - left + 1 - maxCount > k) {
                counts[s[left] - 'A']--;
                left++;
            }
            best = max(best, right - left + 1);
        }
        return best;
    }
};

Complexity Analysis

  • Time: O(n). right visits each character once, and left moves at most once per step.
  • Space: O(1). The counter array has a fixed 26 entries.

Key Insights

  • Cost of a window = length - top count: the best strategy for a fixed window is to keep its most frequent letter and change the rest.
  • Only the maximum length matters: that is why the window is allowed to slide without shrinking.
  • A stale maxCount is safe: after the window first becomes invalid, the answer only grows when maxCount reaches a new high, and that new high is always a real count in the current window.
  • Fixed alphabet: 26 counters make every update O(1), so no hash map is needed.

Edge Cases

  1. k = 0: the answer is the longest run of one repeated letter.
  2. k >= length - top count of the whole string: the entire string can be made uniform, so the answer is n.
  3. Single character: the answer is 1.
  4. All letters equal: the answer is n for any k.
  5. All letters different: the answer is min(n, k + 1).

Common Mistakes

  1. Assuming the current window is always valid: in the non-shrinking version, maxCount can be stale, so the window at a given step may need more than k changes. Only the best length it records is meaningful. If you need the actual substring, save left and right at the moment best increases.
  2. Decreasing maxCount when a letter leaves: not needed, and getting it right requires a full rescan of the counters.
  3. Using length - maxCount < k: the condition is <= k. Exactly k changes is allowed.
  4. Fixing one target letter in advance: you do not know which letter to keep. Either track the max count, or run one sliding window per letter (26 passes, still O(n)).
  5. Reporting right - left instead of right - left + 1: window length is inclusive of both ends.

Interview Tips

  1. Start with the window validity rule length - maxCount <= k. Everything else follows from it.
  2. Present the “shrink with a while loop and rescan for the true max” version if the stale-max idea feels risky, then explain why the non-shrinking window is still correct.
  3. Mention the alternative of 26 passes, one per target letter, each a simple “at most k mismatches” window. It is also O(n) and easy to prove.
  4. Compare with Longest Substring Without Repeating Characters: same sliding-window shape, different validity rule.

Follow-up Questions

  1. Lowercase and uppercase, or full Unicode: replace the 26-entry array with a hash map. The stale-max argument still holds.
  2. Return the substring itself: remember the left and right where best last increased.
  3. Binary version: Max Consecutive Ones III (LC 1004) is the same idea with only two letters, where you flip at most k zeros.
  4. Changes cost different amounts per letter: the window cost is no longer just length - maxCount, and you need to track the cost of converting the window to each candidate letter.