Variable-Size Sliding Window: The Grow/Shrink Template

A variable-size sliding window lets the window grow and shrink so it always satisfies some condition — finding the longest or shortest contiguous range that obeys a rule. You expand the right edge to include more, and contract the left edge whenever the window breaks (or over-satisfies) the constraint. Both edges only ever move forward, so the whole thing stays O(n).

The grow/shrink template

Almost every variable-window problem fits this shape:

l = 0
for r in 0..n-1:
    add a[r] to the window
    while (window is invalid):   # or: while it can shrink and stay valid
        remove a[l] from the window
        l += 1
    update the answer using the current window [l..r]

The two decisions that customize it: what “invalid” means, and whether you record the answer while shrinking or after. Let’s see both classic forms.

Longest substring without repeating characters

Grow r; if the incoming character is already in the window, shrink l until it isn’t. The answer is the largest window width seen.

#include <string>
#include <unordered_map>
#include <algorithm>
int longestUnique(const std::string& s) {
    std::unordered_map<char, int> count;
    int l = 0, best = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        count[s[r]]++;
        while (count[s[r]] > 1) {     // duplicate inside window
            count[s[l]]--;
            l++;
        }
        best = std::max(best, r - l + 1);
    }
    return best;
}

import java.util.HashMap;
import java.util.Map;
int longestUnique(String s) {
    Map<Character, Integer> count = new HashMap<>();
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        count.merge(c, 1, Integer::sum);
        while (count.get(c) > 1) {    // duplicate inside window
            char left = s.charAt(l);
            count.merge(left, -1, Integer::sum);
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

function longestUnique(s) {
  const count = new Map();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    count.set(c, (count.get(c) || 0) + 1);
    while (count.get(c) > 1) {        // duplicate inside window
      count.set(s[l], count.get(s[l]) - 1);
      l++;
    }
    best = Math.max(best, r - l + 1);
  }
  return best;
}

def longest_unique(s):
    count = {}
    l = best = 0
    for r in range(len(s)):
        c = s[r]
        count[c] = count.get(c, 0) + 1
        while count[c] > 1:           # duplicate inside window
            count[s[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

For "abcabcbb" the answer is 3 ("abc").

Minimum window covering a target

Now we want the shortest window of s that contains every character of t (with multiplicity). Grow until the window is valid, then shrink as far as possible while staying valid, recording the smallest width.

#include <string>
#include <unordered_map>
#include <climits>
std::string minWindow(const std::string& s, const std::string& t) {
    if (t.empty() || s.size() < t.size()) return "";
    std::unordered_map<char, int> need;
    for (char c : t) need[c]++;
    int missing = t.size();               // chars still required
    int l = 0, bestLen = INT_MAX, bestL = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        if (need[s[r]]-- > 0) missing--;  // consumed a needed char
        while (missing == 0) {            // window is valid
            if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
            if (++need[s[l]] > 0) missing++;
            l++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
}

import java.util.HashMap;
import java.util.Map;
String minWindow(String s, String t) {
    if (t.isEmpty() || s.length() < t.length()) return "";
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
    int missing = t.length();             // chars still required
    int l = 0, bestLen = Integer.MAX_VALUE, bestL = 0;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        if (need.getOrDefault(c, 0) > 0) missing--;
        need.merge(c, -1, Integer::sum);
        while (missing == 0) {            // window is valid
            if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
            char left = s.charAt(l);
            need.merge(left, 1, Integer::sum);
            if (need.get(left) > 0) missing++;
            l++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
}

function minWindow(s, t) {
  if (!t || s.length < t.length) return "";
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  let missing = t.length;                 // chars still required
  let l = 0, bestLen = Infinity, bestL = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    if ((need.get(c) || 0) > 0) missing--;
    need.set(c, (need.get(c) || 0) - 1);
    while (missing === 0) {                // window is valid
      if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
      const left = s[l];
      need.set(left, need.get(left) + 1);
      if (need.get(left) > 0) missing++;
      l++;
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestL, bestL + bestLen);
}

def min_window(s, t):
    if not t or len(s) < len(t):
        return ""
    need = {}
    for c in t:
        need[c] = need.get(c, 0) + 1
    missing = len(t)                       # chars still required
    l = best_l = 0
    best_len = float("inf")
    for r in range(len(s)):
        c = s[r]
        if need.get(c, 0) > 0:
            missing -= 1
        need[c] = need.get(c, 0) - 1
        while missing == 0:                # window is valid
            if r - l + 1 < best_len:
                best_len, best_l = r - l + 1, l
            need[s[l]] += 1
            if need[s[l]] > 0:
                missing += 1
            l += 1
    return "" if best_len == float("inf") else s[best_l:best_l + best_len]

For s = "ADOBECODEBANC", t = "ABC" the answer is "BANC".

Why it’s O(n)

Each index is added to the window exactly once (when r passes it) and removed at most once (when l passes it). So even though there’s a nested while, the total number of l advances across the whole run is at most n. The result is O(n) time and O(k) space for the frequency map (k = alphabet/key size).

For beginners: The nested while loop scares people into thinking this is O(n²). It isn’t — l never resets and never exceeds n. Count total moves of each pointer, not loops-inside-loops.

Longest vs shortest — where you record the answer

Longest valid window: keep the window valid by shrinking only when it breaks, then record the width after the while.
Shortest valid window: grow until valid, then record inside the while as you shrink to the tightest valid size.

Common pitfalls

Updating the answer at the wrong moment (inside vs outside the shrink loop) — it flips longest into shortest and vice-versa.
Forgetting to undo the left element’s bookkeeping when you advance l.
Negative numbers in sum-based variable windows. “Smallest subarray with sum ≥ target” needs all values non-negative for the monotonic shrink to be valid; with negatives, use prefix sums instead.

Going deeper: This is the same engine behind the sliding window pattern and overlaps with two pointers. Internalize the template and a whole class of string/array problems collapses to a few lines.

Next: precompute range sums with prefix sums, or jump to the exercises.