424. Longest Repeating Character Replacement (Medium)

Problem

Given a string s and an integer k, return the length of the longest substring containing the same letter after you perform at most k character replacements. You may choose which letter to make the string uniform with.

Example

s = "ABAB", k = 2 → 4 (replace both A’s with B or both B’s with A)
s = "AABABBA", k = 1 → 4 (replace the B at index 3; substring "AABA" + replacement = "AAAA")

LeetCode 424 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try every substring

For each substring, count characters and check that (length - max_count) ≤ k.

def character_replacement(s: str, k: int) -> int:
    from collections import Counter
    n = len(s)
    best = 0
    for i in range(n):                           # L1: outer loop, n iterations
        for j in range(i, n):                    # L2: inner loop, O(n) per outer
            counts = Counter(s[i:j + 1])         # L3: slice + Counter, O(n) each
            length = j - i + 1
            if length - max(counts.values()) <= k:  # L4: O(k) max over counts
                best = max(best, length)         # L5: O(1)
    return best

function characterReplacement(s: string, k: number): number {
    const n = s.length;
    let best = 0;
    for (let i = 0; i < n; i++) {                            // L1: outer loop, n iterations
        const counts = new Map<string, number>();
        for (let j = i; j < n; j++) {                        // L2: inner loop, O(n) per outer
            counts.set(s[j], (counts.get(s[j]) ?? 0) + 1);  // L3: O(1) incremental update
            const length = j - i + 1;
            const maxCount = Math.max(...counts.values());    // L4: O(k) max over counts
            if (length - maxCount <= k)
                best = Math.max(best, length);                // L5: O(1)
        }
    }
    return best;
}

func characterReplacement(s string, k int) int {
  n := len(s)
  best := 0
  for i := 0; i < n; i++ {                              // L1: outer loop, n iterations
    counts := make(map[byte]int)
    for j := i; j < n; j++ {                          // L2: inner loop, O(n) per outer
      counts[s[j]]++                                // L3: O(1) incremental update
      length := j - i + 1
      maxCount := 0
      for _, v := range counts {                    // L4: O(k) max over counts
        if v > maxCount {
          maxCount = v
        }
      }
      if length-maxCount <= k && length > best {   // L5: O(1)
        best = length
      }
    }
  }
  return best
}

final class Solution {
    func characterReplacement(_ s: String, _ k: Int) -> Int {
        let characters = Array(s)
        var best = 0
        for start in characters.indices {
            var counts: [Character: Int] = [:], maximum = 0
            for end in start..<characters.count {
                counts[characters[end], default: 0] += 1
                maximum = max(maximum, counts[characters[end], default: 0])
                let length = end - start + 1
                if length - maximum <= k { best = max(best, length) }
            }
        }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(s), k = number of distinct characters in s (≤ alphabet size, at most 26).

Line	Per-call cost	Times executed	Contribution
L1 (outer loop)	$O(1)$	n	$O(n)$
L2 (inner loop)	$O(1)$	$O(n²)$ total	$O(n²)$
L3 (Counter build)	$O(n)$	$O(n²)$	$O(n³)$ ← dominates
L4 (max over counts)	$O(k)$	$O(n²)$	$O(n² · k)$

L3 allocates a new slice and builds a Counter for every (i, j) pair, which is $O(n)$ work done $O(n²)$ times.

Complexity

Time: $O(n³)$ , driven by L3 (Counter on every substring pair).
Space: $O(k)$ where k = alphabet size.

Approach 2: Per-target-letter sliding window

For each possible target letter (A-Z, so at most 26), slide a window that keeps the count of non-target characters ≤ k.

def character_replacement(s: str, k: int) -> int:
    best = 0
    for target in set(s):                   # L1: at most 26 targets
        left = 0
        non_target = 0
        for right in range(len(s)):         # L2: inner loop, n iterations per target
            if s[right] != target:          # L3: O(1) character check
                non_target += 1            # L4: O(1)
            while non_target > k:          # L5: shrink window
                if s[left] != target:
                    non_target -= 1        # L6: O(1)
                left += 1                  # L7: O(1)
            best = max(best, right - left + 1)  # L8: O(1)
    return best

function characterReplacement(s: string, k: number): number {
    let best = 0;
    const chars = new Set(s);
    for (const target of chars) {                   // L1: at most 26 targets
        let left = 0, nonTarget = 0;
        for (let right = 0; right < s.length; right++) {  // L2: n iterations per target
            if (s[right] !== target) nonTarget++;   // L3/L4: O(1)
            while (nonTarget > k) {                 // L5: shrink window
                if (s[left] !== target) nonTarget--;// L6: O(1)
                left++;                             // L7: O(1)
            }
            best = Math.max(best, right - left + 1);// L8: O(1)
        }
    }
    return best;
}

func characterReplacement(s string, k int) int {
  best := 0
  seen := make(map[byte]bool)
  for i := 0; i < len(s); i++ {
    seen[s[i]] = true
  }
  for target := range seen {                         // L1: at most 26 targets
    left, nonTarget := 0, 0
    for right := 0; right < len(s); right++ {     // L2: n iterations per target
      if s[right] != target {                   // L3/L4: O(1)
        nonTarget++
      }
      for nonTarget > k {                       // L5: shrink window
        if s[left] != target {               // L6: O(1)
          nonTarget--
        }
        left++                               // L7: O(1)
      }
      if right-left+1 > best {                 // L8: O(1)
        best = right - left + 1
      }
    }
  }
  return best
}

final class Solution {
    func characterReplacement(_ s: String, _ k: Int) -> Int {
        let characters = Array(s)
        var best = 0
        for target in Set(characters) {
            var left = 0, replacements = 0
            for right in characters.indices {
                if characters[right] != target { replacements += 1 }
                while replacements > k { if characters[left] != target { replacements -= 1 }; left += 1 }
                best = max(best, right - left + 1)
            }
        }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(s), k = number of distinct characters in s (≤ 26).

Line	Per-call cost	Times executed	Contribution
L1 (targets loop)	$O(1)$	up to 26	$O(26)$
L2 (inner loop)	$O(1)$ body	n per target	$O(26n)$ = $O(n)$ ← dominates
L5-L7 (shrink)	$O(1)$ amortized	at most n per target	$O(26n)$ = $O(n)$
L8 (best update)	$O(1)$	n per target	$O(26n)$ = $O(n)$

The outer loop runs at most 26 times (26-character alphabet). For each target, left advances at most n times total across all iterations of L5-L7. So the total work per target is $O(n)$ , and $O(26n)$ overall.

Complexity

Time: $O(26 · n)$ = $O(n)$ , driven by L2 (n iterations for each of the 26 targets).
Space: $O(1)$ .

Already optimal in Big-O; the third approach drops the constant factor of 26.

Approach 3: Single sliding window with running max-frequency (optimal)

Maintain one window and a count of each character in it. Track max_freq, the most frequent character in the window. Shrinking is needed when (window_length - max_freq) > k.

Key insight: we never need to decrease max_freq as left advances. A smaller max-freq would only matter if it produced a larger window, which the current best already captured.

def character_replacement(s: str, k: int) -> int:
    from collections import Counter
    counts = Counter()
    left = 0
    max_freq = 0
    best = 0
    for right, ch in enumerate(s):                      # L1: outer loop, n iterations
        counts[ch] += 1                                  # L2: O(1)
        max_freq = max(max_freq, counts[ch])             # L3: O(1) running max
        while (right - left + 1) - max_freq > k:        # L4: shrink if too many replacements
            counts[s[left]] -= 1                        # L5: O(1)
            left += 1                                   # L6: O(1)
        best = max(best, right - left + 1)              # L7: O(1)
    return best

function characterReplacement(s: string, k: number): number {
    const counts = new Map<string, number>();
    let left = 0;
    let maxFreq = 0;
    let best = 0;
    for (let right = 0; right < s.length; right++) {    // L1: outer loop, n iterations
        const ch = s[right];
        counts.set(ch, (counts.get(ch) ?? 0) + 1);      // L2: O(1)
        maxFreq = Math.max(maxFreq, counts.get(ch)!);   // L3: O(1) running max
        while ((right - left + 1) - maxFreq > k) {     // L4: shrink if too many replacements
            counts.set(s[left], counts.get(s[left])! - 1);  // L5: O(1)
            left++;                                     // L6: O(1)
        }
        best = Math.max(best, right - left + 1);        // L7: O(1)
    }
    return best;
}

func characterReplacement(s string, k int) int {
  counts := make(map[byte]int)
  left := 0
  maxFreq := 0
  best := 0
  for right := 0; right < len(s); right++ {           // L1: outer loop, n iterations
    ch := s[right]
    counts[ch]++                                     // L2: O(1)
    if counts[ch] > maxFreq {                        // L3: O(1) running max
      maxFreq = counts[ch]
    }
    for (right-left+1)-maxFreq > k {                // L4: shrink if too many replacements
      counts[s[left]]--                            // L5: O(1)
      left++                                       // L6: O(1)
    }
    if right-left+1 > best {                         // L7: O(1)
      best = right - left + 1
    }
  }
  return best
}

final class Solution {
    func characterReplacement(_ s: String, _ k: Int) -> Int {
        let characters = Array(s)
        var counts: [Character: Int] = [:]
        var left = 0, maximumFrequency = 0, best = 0
        for right in characters.indices {
            counts[characters[right], default: 0] += 1
            maximumFrequency = max(maximumFrequency, counts[characters[right], default: 0])
            while right - left + 1 - maximumFrequency > k { counts[characters[left], default: 0] -= 1; left += 1 }
            best = max(best, right - left + 1)
        }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(s), k = number of distinct characters in s (≤ 26).

Line	Per-call cost	Times executed	Contribution
L1 (expand right)	$O(1)$ body	n	$O(n)$ ← dominates
L2/L3 (update counts + max_freq)	$O(1)$	n	$O(n)$
L4-L6 (shrink left)	$O(1)$ amortized	at most n total	$O(n)$
L7 (best update)	$O(1)$	n	$O(n)$

The key insight for L3: we never decrease max_freq even when shrinking. This is safe because a smaller max_freq could only produce a window no larger than the current best, so there’s no value in tracking the exact maximum after a shrink. left advances at most n times total across the whole run (amortized $O(1)$ per step).

Complexity

Time: $O(n)$ , driven by L1 (single pass; left and right each advance at most n times total).
Space: $O(k)$ for the counter (at most alphabet size).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Brute force	$O(n³)$	$O(k)$
Per-letter sliding window	$O(26 · n)$ = $O(n)$	$O(1)$
Single sliding window	$O(n)$	$O(k)$

The max-freq trick is the hallmark of this problem: it lets us skip the “decrement max_freq when shrinking” step entirely, because it only affects candidate windows that are shorter than what we’ve already seen.

Test cases

# Quick smoke tests - paste into a REPL or save as test_424.py and run.
# Uses the optimal Approach 3 implementation.

from collections import Counter

def character_replacement(s: str, k: int) -> int:
    counts = Counter()
    left = 0
    max_freq = 0
    best = 0
    for right, ch in enumerate(s):
        counts[ch] += 1
        max_freq = max(max_freq, counts[ch])
        while (right - left + 1) - max_freq > k:
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

def _run_tests():
    assert character_replacement("ABAB", 2) == 4      # replace both A's or both B's
    assert character_replacement("AABABBA", 1) == 4   # "AABA" with one replacement
    assert character_replacement("A", 0) == 1         # single char
    assert character_replacement("AAAA", 2) == 4      # already uniform
    assert character_replacement("ABCDE", 1) == 2     # any two adjacent, only 1 replacement
    assert character_replacement("AABBA", 2) == 5     # full string with 2 replacements
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function characterReplacement(s: string, k: number): number {
    const counts = new Map<string, number>();
    let left = 0, maxFreq = 0, best = 0;
    for (let right = 0; right < s.length; right++) {
        const ch = s[right];
        counts.set(ch, (counts.get(ch) ?? 0) + 1);
        maxFreq = Math.max(maxFreq, counts.get(ch)!);
        while ((right - left + 1) - maxFreq > k) {
            counts.set(s[left], counts.get(s[left])! - 1);
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

console.assert(characterReplacement("ABAB", 2) === 4);
console.assert(characterReplacement("AABABBA", 1) === 4);
console.assert(characterReplacement("A", 0) === 1);
console.assert(characterReplacement("AAAA", 2) === 4);
console.assert(characterReplacement("ABCDE", 1) === 2);
console.assert(characterReplacement("AABBA", 2) === 5);
console.log("all tests pass");

func characterReplacement(s string, k int) int {
  counts := make(map[byte]int)
  left, maxFreq, best := 0, 0, 0
  for right := 0; right < len(s); right++ {
    ch := s[right]
    counts[ch]++
    if counts[ch] > maxFreq {
      maxFreq = counts[ch]
    }
    for (right-left+1)-maxFreq > k {
      counts[s[left]]--
      left++
    }
    if right-left+1 > best {
      best = right - left + 1
    }
  }
  return best
}

Strings, input
Hash Tables, frequency counts inside the window

Monotonic Queue, deque tactics for maintaining a window minimum or maximum as the window slides.
Sliding Window, contiguous-range tactics for maintaining a valid subarray or substring while endpoints move forward.

424. Longest Repeating Character Replacement (Medium)

Problem

Try it yourself

Approach 1: Brute force, try every substring

Approach 2: Per-target-letter sliding window

Approach 3: Single sliding window with running max-frequency (optimal)

Summary

Test cases

Related data structures

Related concepts