Sliding Windows: Character Replacement and Minimum Window Substring

Two Window Goals: Allow Replacements or Cover Required Characters

The code in advanced window problems often looks dense because several counters are updated together. The underlying process is still the same:

1. define exactly what makes a window valid;
2. choose state that can answer that question without rescanning;
3. update the state when one character enters or leaves;
4. expand or shrink according to the objective.

Do not begin by copying a template containing names such as formed, required, or maxFrequency. Give each variable a sentence describing what it means. The names become useful only after the meaning is established.

Character Replacement: Allow at Most k Changes

Suppose you may replace at most k characters in a substring, and you want the longest substring that can be made from one repeated character.

Consider the window AABAB:

window length = 5
most common character = A, appearing 3 times
other characters = 5 - 3 = 2

Changing the two Bs to As makes the whole window uniform. The number of replacements needed is therefore:

window length - frequency of its most common character

The window is valid when:

window length - maxFrequency <= k

Start with the clearest correct implementation

For uppercase English letters, keep 26 counts. After adding or removing a character, scanning those 26 values gives the current maximum frequency. Since 26 is fixed, that scan is constant work.

function uppercaseIndex(character: string): number {
  return character.charCodeAt(0) - "A".charCodeAt(0)
}

function largestCount(counts: number[]): number {
  let largest = 0
  for (const count of counts) largest = Math.max(largest, count)
  return largest
}

function characterReplacement(text: string, k: number): number {
  const counts = new Array<number>(26).fill(0)
  let left = 0
  let best = 0

  for (let right = 0; right < text.length; right += 1) {
    counts[uppercaseIndex(text[right])] += 1

    while (right - left + 1 - largestCount(counts) > k) {
      counts[uppercaseIndex(text[left])] -= 1
      left += 1
    }

    best = Math.max(best, right - left + 1)
  }

  return best
}

This is O(26n), which is O(n) because the alphabet size is fixed. It is often better to explain this version first than to introduce a clever optimization whose correctness is unclear.

Trace: "AABABBA", k = 1

window A       → dominant A count 1, replacements 0, valid
window AA      → dominant A count 2, replacements 0, valid
window AAB     → dominant A count 2, replacements 1, valid
window AABA    → dominant A count 3, replacements 1, valid, best 4
window AABAB   → dominant A count 3, replacements 2, invalid
shrink left    → window ABAB, dominant count 2, replacements 2, still invalid
shrink again   → window BAB, dominant B count 2, replacements 1, valid

The important idea is the validity equation, not the particular counter implementation.

Minimum Window Substring: Include Every Required Character

Minimum Window Substring asks for the shortest substring of source containing every character required by target, including duplicates.

If the target is "AABC", a valid window needs:

A → at least 2
B → at least 1
C → at least 1

A Set is insufficient because it cannot distinguish one A from two. A frequency map stores each required quantity.

const needed = new Map<string, number>()
for (const character of target) {
  needed.set(character, (needed.get(character) ?? 0) + 1)
}

Count satisfied categories, not merely characters

Suppose needed contains requirements for A, B, and C. Then:

requiredKinds = 3

Maintain a second map for the current window. A character category becomes satisfied at the exact moment its window count reaches its needed count.

For target "AABC":

window count of A changes 1 → 2  : A becomes satisfied
window count of A changes 2 → 3  : still satisfied; do not count it again
window count of A changes 2 → 1  : A stops being satisfied

Let formedKinds count how many distinct requirements are currently satisfied. The window is valid when:

formedKinds === requiredKinds

This comparison is constant time. It replaces a repeated scan over the entire requirement map.

Expand to become valid, shrink to become minimal

The outer loop expands right until the window covers every requirement. Once valid, the inner loop records the candidate and removes characters from the left. Irrelevant characters and surplus required characters can disappear without breaking validity. Eventually one necessary count falls below its requirement; then expansion resumes.

function minWindow(source: string, target: string): string {
  if (target.length === 0 || target.length > source.length) return ""

  const needed = new Map<string, number>()
  for (const character of target) {
    needed.set(character, (needed.get(character) ?? 0) + 1)
  }

  const window = new Map<string, number>()
  const requiredKinds = needed.size
  let formedKinds = 0
  let left = 0
  let bestStart = 0
  let bestLength = Infinity

  for (let right = 0; right < source.length; right += 1) {
    const incoming = source[right]
    window.set(incoming, (window.get(incoming) ?? 0) + 1)

    if (needed.has(incoming) && window.get(incoming) === needed.get(incoming)) {
      formedKinds += 1
    }

    while (formedKinds === requiredKinds) {
      const length = right - left + 1
      if (length < bestLength) {
        bestLength = length
        bestStart = left
      }

      const outgoing = source[left]
      window.set(outgoing, window.get(outgoing)! - 1)

      if (needed.has(outgoing) && window.get(outgoing)! < needed.get(outgoing)!) {
        formedKinds -= 1
      }

      left += 1
    }
  }

  return bestLength === Infinity
    ? ""
    : source.slice(bestStart, bestStart + bestLength)
}

Worked story: "ADOBECODEBANC" needs "ABC"

The first valid window is "ADOBEC": it contains one A, one B, and one C. Shrinking from the left immediately removes the only A, so the window becomes invalid.

Expansion continues until another A appears:

"DOBECODEBA"

This window contains the requirements. Shrinking removes irrelevant and surplus characters from its left. Later, after the final C arrives, the valid window can shrink to:

"BANC"

Removing B would break its requirement, so "BANC" is minimal for that ending position. It is also shorter than every earlier valid window, so it becomes the final answer.

Compare the two advanced windows

Both are linear because left and right move only forward. Character Replacement uses O(1) space for a fixed alphabet. Minimum Window uses O(d) space, where d is the number of distinct characters stored.

Final checkpoint: narrate the counters

Before coding, complete these sentences:

• “This map stores…”
• “This counter increases exactly when…”
• “The window becomes invalid when…”
• “Removing the left character changes…”
• “I record an answer before/after shrinking because…”

If a variable cannot be described without referring to the code that updates it, its role is not yet clear enough.