Stage 1: Foundations·Two Pointers & Sliding Window

Hard#768 min readSliding WindowHashingLeetCode

Minimum Window Substring

Counter-Based Sliding Window

The ‘hard’ sliding window — but if you understood #3, this is the same pattern with a counter.

Published Apr 15, 2026

Problem

Given two strings s and t, return the minimum window substring of s such that every character in t appears in the window with the same multiplicity.

If no such window exists, return the empty string "".

Input

s = "ADOBECODEBANC", t = "ABC"

Output

"BANC"

Explanation

BANC is the smallest substring containing A, B, and C.

Input

s = "a", t = "a"

Output

"a"

Input

s = "a", t = "aa"

Output

Intuition

This problem is a sliding window, but not the "find a substring with no duplicates" version from #3. Here the window is valid only when it contains enough of every required character.

So instead of a boolean invariant, we maintain a deficit counter:

need[c] tells us how many more of character c the window still needs.
When we add a character on the right, we reduce its deficit.
When all deficits are satisfied, we try to shrink from the left as much as possible while staying valid.

That gives us the minimum window for every right boundary, and the best among those is the answer.

Interactive concept

Minimum Window Deficit

The window is valid exactly when every required character deficit is paid down.

Start with a debt

The target ABC creates three missing units. Expanding right pays them down.

missing2

Target invariant: need[A]=1, need[B]=1, need[C]=1

A0LR

A10

N11

C12

Approach

Counter-Based Sliding Window

TimeO(n + m)

SpaceO(1)

Recommended

Build the requirement counts from t, then sweep s with two pointers.

Expand right until the window covers t.
Once valid, shrink left while the window still covers t.
Record the smallest valid window seen so far.

The window is valid when the number of still-missing characters reaches zero. Repeated characters are handled automatically because the counter tracks multiplicity, not just presence.

impl Solution {
    pub fn min_window(s: String, t: String) -> String {
        if t.len() > s.len() {
            return String::new();
        }

        let sb = s.as_bytes();
        let tb = t.as_bytes();
        let mut need = [0i32; 128];
        for &b in tb {
            need[b as usize] += 1;
        }

        let mut missing = tb.len() as i32;
        let mut left = 0usize;
        let mut best_len = usize::MAX;
        let mut best_start = 0usize;

        for right in 0..sb.len() {
            let idx = sb[right] as usize;
            need[idx] -= 1;
            if need[idx] >= 0 {
                missing -= 1;
            }

            while missing == 0 {
                let window_len = right - left + 1;
                if window_len < best_len {
                    best_len = window_len;
                    best_start = left;
                }

                let left_idx = sb[left] as usize;
                need[left_idx] += 1;
                if need[left_idx] > 0 {
                    missing += 1;
                }
                left += 1;
            }
        }

        if best_len == usize::MAX {
            String::new()
        } else {
            s[best_start..best_start + best_len].to_string()
        }
    }
}

Rust · runnable

function minWindow(s: string, t: string): string {
  if (t.length > s.length) return "";

  const need = new Int32Array(128);
  for (let i = 0; i < t.length; i++) {
    need[t.charCodeAt(i)]++;
  }

  let missing = t.length;
  let left = 0;
  let bestLen = Number.POSITIVE_INFINITY;
  let bestStart = 0;

  for (let right = 0; right < s.length; right++) {
    const r = s.charCodeAt(right);
    need[r]--;
    if (need[r] >= 0) missing--;

    while (missing === 0) {
      const windowLen = right - left + 1;
      if (windowLen < bestLen) {
        bestLen = windowLen;
        bestStart = left;
      }

      const l = s.charCodeAt(left);
      need[l]++;
      if (need[l] > 0) missing++;
      left++;
    }
  }

  return Number.isFinite(bestLen) ? s.slice(bestStart, bestStart + bestLen) : "";
}

TypeScript · runnable

The important detail is the sign convention on need: positive means the window is still missing that many characters, zero means satisfied, negative means the window has surplus copies.

Trace

For s = "ADOBECODEBANC", t = "ABC":

Sliding window#76

Minimum Window Substring walkthrough

s = ADOBECODEBANC, t = ABC

Step 1 of 30%

Sliding window state

missing = 0

Scan right until A, B, and C have all appeared.

Pay down required characters

Decision

Characters D, O, and E are surplus; A, B, and C reduce missing.

Update

At right = 5, missing becomes 0 and ADOBEC is the first valid window.

Why it works

Validity is tied to deficits, not to the raw window length.

Bug prevented

Counting distinct seen characters breaks when t has duplicate letters.

Micro-steps

Gain A

need[A] moves from 1 to 0, so missing drops to 2.

Gain B

need[B] moves from 1 to 0, so missing drops to 1.

Gain C

need[C] moves from 1 to 0, so missing drops to 0.

The first valid window is not the answer; it is only the first chance to shrink.

Edge cases

No possible window returns "".
Repeated letters in t matter. t = "AABC" requires two As, not one.
t longer than s can short-circuit immediately.
Surplus characters inside the window are allowed as long as the deficits stay covered.

💡

Tip

If #3 is "maintain a set of characters that are inside the window," #76 is "maintain a multiset of required characters that the window still owes." Same loop, stricter invariant.

Takeaway

The difference between easy and hard sliding window problems is usually the invariant, not the loop shape.

Once you can phrase the window state as a counter of remaining requirements, minimum-window problems stop being mysterious and become a mechanical shrink-and-record scan.

Medium#3

Longest Substring Without Repeating Characters

Your first sliding window. When do you shrink vs expand?

Easy#125

Valid Palindrome

Converging pointers from both ends. Simple but builds the muscle memory.

Medium#167

Two Sum II - Sorted

Why does moving the left pointer increase the sum? Understand the proof.