LeetCode 424 · Sliding Window

Longest Repeating Character Replacement, explained with a picture

Repainting a few fence planks.

MediumSliding Window
▶ Watch it step by step

The problem

Given a string of capital letters and a number k, you may change up to k letters into any other letter. What is the length of the longest stretch you can make where all letters are the same?

Input:  s = "AABABBA", k = 1
Output: 4   (repaint the B in "AABA" to get "AAAA")

Picture it

Picture a fence of coloured planks and a small can of paint that can repaint k planks. Inside a window of planks, the cheapest plan is to keep the most common colour and repaint everything else. If “window length − most common count” is more than k, we don’t have enough paint, so we slide the left edge forward.

How to recognise it

  • The answer is the longest contiguous stretch that satisfies a rule, so think sliding window.
  • The rule is "at most k letters need changing". In a window, the cheapest fix keeps the most common letter and changes the rest: (window length) − (top count) changes.
  • The rule is monotone: if a window needs more than k changes, any bigger window containing it does too. So you can grow on the right and shrink on the left.
  • Up to 10^5 capital letters, so checking every substring is too slow.

Start with brute force

From every start, extend to the right, keep letter counts, and record the window whenever it needs at most k changes.

from collections import Counter

def character_replacement_brute(s, k):
    best = 0
    for i in range(len(s)):
        count = Counter()
        for j in range(i, len(s)):
            count[s[j]] += 1
            if (j - i + 1) - max(count.values()) <= k:
                best = max(best, j - i + 1)
    return best

There are about n²/2 windows, and each check scans up to 26 counts, so time is O(26 · n²). With n = 10^5 that is over 10^11 steps. Space is O(1), as at most 26 letters are counted.

From brute force to the idea

  1. Find the waste. Each start rebuilds its counts from nothing, even though neighbouring windows share almost every letter.
  2. Slide one window. Move right one letter at a time and add it to count. If the window needs more than k changes, drop letters from the left until it does not.
  3. Track the top count cheaply. top is the highest count any letter has reached. Updating it with the letter that just entered is O(1), instead of scanning 26 counts.
  4. Never lower top. When letters leave, top may now be too high for the current window. That is safe: the window can then only be as long as top + k, a length already achieved by a real valid window. best only grows when some letter reaches a new, higher count.
  5. Record after shrinking. The window right - left + 1 is a candidate on every step.

This is the key idea: a window whose length minus its top letter count must stay at most k, with the top count only ever going up.

The key idea

A window is fine while (length − count of its most frequent letter) ≤ k. Grow right, shrink left when it breaks. O(n).

Python solution

def character_replacement(s, k):
    count, left, top, best = Counter(), 0, 0, 0
    for right, ch in enumerate(s):
        count[ch] += 1
        top = max(top, count[ch])         # most common colour in window
        while (right - left + 1) - top > k:  # too many planks to repaint
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(26 · n²): every window, each with a scan of the countsO(1): at most 26 counts
Sliding window (shown code)O(n): right and left each move forward at most n timesO(1): at most 26 counts

Edge cases

  • k = 0 ("AAAB"): returns 3, the longest run of one letter.
  • k at least the length ("ABC", k = 5): returns 3, the whole string.
  • Example ("AABABBA", k = 1): returns 4.
  • All different, k = 0 ("ABCD"): returns 1.
  • Empty string: returns 0. LeetCode guarantees at least one letter.
  • Missing import: the code needs from collections import Counter; without it the call raises NameError.

Common mistakes

  • Recomputing max(count.values()) on every step. Correct, but 26 times more work per step; the stale top is enough.
  • Lowering top when letters leave and then trying to keep it exact, which is complicated and unnecessary.
  • Comparing the number of distinct letters with k, instead of the number of letters that are not the most common one.
  • Worrying that the while should be an if. Both give the same answer here: the window grows by one per step and top never falls, so one step left always restores the rule.
Your turn: flip at most k zeros

Given a list of 0s and 1s and a number k, return the longest stretch of 1s you can get by flipping at most k zeros. For [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0] with k = 2 the answer is 6. Describe your approach, then write it if you like.

Compare with our answer

This is the same problem with only two "letters", where you always keep 1. So the number of changes is simply the number of zeros in the window. Grow on the right, count zeros, and shrink from the left while there are more than k.

def longest_ones(nums, k):
    left = zeros = best = 0
    for right, x in enumerate(nums):
        zeros += x == 0
        while zeros > k:
            zeros -= nums[left] == 0
            left += 1
        best = max(best, right - left + 1)
    return best

No top is needed, because the letter you keep is fixed. Time O(n), space O(1).

A strong answer mentions: that the zero count is the number of changes, shrinking while it exceeds k, and why each element enters and leaves the window once.

Check what stuck

1. Fence planks have colours given as integers up to 10^9. Find the longest run of planks you can make one colour by repainting at most k of them. Which approach fits best?

2. Why is the shown code O(n) rather than O(26 · n)?

3. A learner changes while to if in the shown code. What happens?

Score 60% or more and the lesson is marked complete.