// Minimum Window Substring

task

Given strings s and t, return the shortest substring of s that contains every character of t (with at least the multiplicity t requires — two 'A's in t means at least two 'A's in the window). Return "" if no such window exists.

s = "ADOBECODEBANC", t = "ABC"  →  "BANC"

how to think

This is a shortest problem, and it needs two dictionaries: need (built once from t — character to required count) and window (built incrementally as right scans s). A window is valid when every character need asks for has been matched in window — track that with a single counter, have, that increments each time a character in window first reaches its required count in need. Expand right until have == need.Count; the moment it does, the window is valid, so shrink left as far as possible while it stays valid, recording the length on every step of the shrink — the smallest length recorded before validity breaks is the answer.

Shrink-while-valid is the mirror image of the two problems before this one: there, growing past the invalid point never helps, so you hold the window open. Here, a smaller valid window is strictly better, so you give up ground as long as you’re still allowed to.

solution

public string MinWindow(string s, string t)
{
    if (t.Length == 0 || s.Length < t.Length) return "";

    var need = new Dictionary<char, int>();
    foreach (char c in t) need[c] = need.GetValueOrDefault(c) + 1;

    var window = new Dictionary<char, int>();
    int have = 0, needCount = need.Count;
    int left = 0, bestLen = int.MaxValue, bestStart = 0;

    for (int right = 0; right < s.Length; right++)
    {
        char c = s[right];
        window[c] = window.GetValueOrDefault(c) + 1;
        if (need.ContainsKey(c) && window[c] == need[c]) have++;   // this char JUST reached its required count

        while (have == needCount)                    // shrink while VALID, recording as we go
        {
            if (right - left + 1 < bestLen)
            {
                bestLen = right - left + 1;
                bestStart = left;
            }
            char lc = s[left];
            window[lc]--;
            if (need.ContainsKey(lc) && window[lc] < need[lc]) have--;  // this char just fell BELOW its required count
            left++;
        }
    }
    return bestLen == int.MaxValue ? "" : s.Substring(bestStart, bestLen);
}

trace

s = "ADOBECODEBANC" (indices 0-12), t = "ABC" → need = {A:1, B:1, C:1}, needCount = 3:

Result: "BANC" (s[9..12]).

right = 5: the first valid window closes — have hits 3/3 for the first time —

right = 12: after two more shrinks past the length-6 detour at right=10, the true minimum lands on indices 9-12 —

why it works

have == needCount is exactly “every required character has met its quota” — no more, no less; have only rises when a character reaches its quota (not on every increment) and only falls when a character drops below it, so it’s a precise validity flag, not an approximation. Because the while shrinks on every right where the window is valid, and records the length before each shrink, every valid window that ever exists gets measured — you can’t skip past a shorter answer, because shrinking one step at a time never jumps over a length. right and left each advance at most n times across the whole run, so despite the nested loop this is O(n) — the right=10 row above shows the “aha”: one step of right can trigger five shrinks in a row, and that’s fine, because those five shrinks are still bounded by left’s total lifetime budget of n.

common bugs

• Comparing window[c] == need[c] for the have++ check but forgetting the mirrored window[lc] < need[lc] for have-- — a naive != on the way down double-counts characters that overshoot their quota (e.g. three 'B's in the window when only one is needed).
• Recording the best length after the shrink instead of before — that measures the post-shrink (possibly invalid) window, not the valid one you just found.
• Using if instead of while for the shrink — a single shrink might still leave the window valid (see right=12, where three shrinks happen back to back), and stopping early misses shorter answers.
• Forgetting the t.Length == 0 || s.Length < t.Length guard — an impossible case that should short-circuit to "", not run the whole scan for nothing.
• Building need fresh inside the loop instead of once before it — need is fixed for the whole run; only window and have change per iteration.

variants you can now solve

• Longest Repeating Character Replacement (LC 424) — the shrink-while-invalid mirror image: there, more is always fine until it isn’t; here, less is always better until it can’t be.
• Substring with Concatenation of All Words (LC 30) — same need/have counting, but the unit is a whole word instead of a character, and the window size is fixed at words.Count * word.Length.
• Permutation in String (LC 567) — a fixed-size version of the same need/have counting: no shrinking at all, just slide and compare have == needCount at each fixed-size position.