A log searcher had to return the shortest contiguous slice that contained every required error code — A, B, and C hiding inside a noisy line. The first version nested every i..j, recounted the slice against t, and kept the shortest cover. A 13-character line returned instantly. A day’s dump was still checking every window when the job was killed.

Return the smallest contiguous window of s that covers every character of t, including duplicates. Nested cover checks use a string and still pay cubic time — quadratic if the inner count is running.

This is an interview writeup, not a sliding-window lecture. The sliding window post owns grow and shrink. The hash table post owns buckets. Here we only care about a variable window whose invariant is cover: grow right until every needed count is met, then shrink left while the cover still holds. Permutation in String is a fixed window of length t that must match exactly — an anagram, not a cover.

The problem

Given strings s (haystack) and t (need), return the shortest contiguous substring of s that contains every character of t with at least t’s multiplicity. If no window covers t, return "". Mixed-case ASCII is the usual board constraint; a follow-up widens it.

s = "ADOBECODEBANC", t = "ABC"  →  "BANC"
s = "a",             t = "a"    →  "a"
s = "a",             t = "aa"   →  ""     need two a's; s has one

Note: Extra letters in the window are allowed. Presence is not enough: t = "aa" is not covered by one a. Find All Anagrams in a String wants every exact window of length t. This prompt wants the shortest cover, and that window is usually longer than t.

Nested cover checks are the honest brute force

For every start i, grow j, and ask whether s[i..j] meets t’s counts. Recount from scratch is cubic; a running count from i is quadratic. Correct, and still the wrong bill.

String minWindowNested(String s, String t) {
    int n = s.length();
    String best = "";
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (covers(s, i, j, t)) {
                int len = j - i + 1;
                if (best.isEmpty() || len < best.length()) {
                    best = s.substring(i, j + 1);
                }
            }
        }
    }
    return best;
}

boolean covers(String s, int i, int j, String t) {
    int[] need = new int[128];
    for (int k = 0; k < t.length(); k++) {
        need[t.charAt(k)]++;
    }
    for (int k = i; k <= j; k++) {
        need[s.charAt(k)]--;
    }
    for (int c = 0; c < 128; c++) {
        if (need[c] > 0) {
            return false;
        }
    }
    return true;
}

At n = 20 this is a rounding error. At a day’s logs you paid a nested scan for a question one grow/shrink pass answers: grow until t is covered, shrink while it still is, record the shortest range.

Right grows until t is covered; left shrinks while the cover holds

Count t into need[128]. required is how many distinct characters t actually uses. The window has have counts and formed — how many of those distinct keys currently meet their need. Characters in s that are not in t still sit between left and right; they never bump formed.

right walks s. Increment have. If this character is needed and its have just hit need, formed++. While formed == required, the window covers: if it is shorter than bestLen, store bestStart and bestLen — do not substring yet. Then drop s.charAt(left) and move left. If a needed character falls below its need, formed-- and the while stops.

Walk "ADOBECODEBANC" with t = "ABC":

s = A D O B E C O D E B  A  N  C
    0 1 2 3 4 5 6 7 8 9 10 11 12
t = ABC   need A:1 B:1 C:1   required=3

right=0 A        formed=1
right=1..4 D,O,B,E   formed=2 after B; D/O/E not in t
right=5 C        formed=3  COVER [0..5] ADOBEC len=6  best
                 drop A → formed=2  left=1   (cover broke; stop)

right=6..9 O,D,E,B   extra B; still missing A
right=10 A       formed=3  COVER [1..10] len=10
                 shrink junk D,O, extra B, E, then C
                 left=6  formed=2  (dropped the only C)
                 best still 6  (CODEBA tied, not shorter)

right=11 N       formed=2
right=12 C       formed=3  COVER [6..12] ODEBANC len=7
                 drop O, D  →  EBANC len=5  best
                 drop E     →  BANC  len=4  best
                 drop B     →  formed=2  stop

The Java is that walk. bestLen starts at n + 1 so a full-string cover still records:

String minWindow(String s, String t) {
    int n = s.length();
    int m = t.length();
    if (m == 0 || m > n) {
        return "";
    }
    int[] need = new int[128];
    int[] have = new int[128];
    int required = 0;
    for (int i = 0; i < m; i++) {
        if (need[t.charAt(i)]++ == 0) {
            required++;
        }
    }
    int formed = 0;
    int left = 0;
    int bestStart = 0;
    int bestLen = n + 1;
    for (int right = 0; right < n; right++) {
        char c = s.charAt(right);
        have[c]++;
        if (need[c] > 0 && have[c] == need[c]) {
            formed++;
        }
        while (formed == required) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            char d = s.charAt(left);
            have[d]--;
            if (need[d] > 0 && have[d] < need[d]) {
                formed--;
            }
            left++;
        }
    }
    return bestLen == n + 1 ? "" : s.substring(bestStart, bestStart + bestLen);
}

Time is O(n + m) — build need from t, then each index of s enters and leaves at most once. Space is O(1) for 128 slots. A map pays extra space if the follow-up opens Unicode.

Note: Shrink while the cover holds, not once. Extra copies of a needed letter are what let left move — "BANC" only appears after a second A and a second C free the earlier edges. Characters not in t stay in the window and do not change formed. Record bestStart and bestLen; copy the slice once at the end. t = "aa" against "a" never reaches formed == required.

What interviewers usually poke next

  • Permutation in String. Fixed length, exact anagram of t. Extra letters fail. Do not solve a cover with that window.
  • Find All Anagrams in a String. Every exact window of length t, not the shortest cover.
  • Longest Repeating Character Replacement. Same grow/shrink, different invariant: spare k mismatches, not cover a target.
  • Map instead of int[128]. Same formed / required. Compare counts with intValue() (or equals); Integer == Integer is a trap past 127.
  • Empty t / null. The guard above returns "" for empty t. Some definitions treat an empty need as an empty window. Null: production would reject. Ask.

You are done with this problem when you can say, out loud, why nested cover checks are correct, why left keeps moving while formed == required, why duplicates in t are a count not a presence bit, and why you store a start and a length instead of copying the slice on every shrink.