Minimum window substring

A variable-size sliding window with a character-count map: grow the right edge until every needed letter is covered, then shrink the left edge as far as it will go.

The idea

need counts every character required by t. window counts what the current [left, right] slice holds. formed counts how many distinct characters already have enough copies. Once formed equals the number of distinct characters needed, the window is valid, so shrink it from the left to look for something smaller before growing again.

Code

public static string MinWindow(string s, string t) {
    var need = new Dictionary<char, int>();
    foreach (char c in t) need[c] = need.GetValueOrDefault(c) + 1;
    int required = need.Count, formed = 0, left = 0;
    var window = new Dictionary<char, int>();
    int 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]) formed++;
        while (formed == required) {
            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]) formed--;
            left++;
        }
    }
    return bestLen == int.MaxValue ? "" : s.Substring(bestStart, bestLen);
}

Tips

• A character only increases formed the moment its count exactly reaches what is needed, not every time it appears.
• Shrinking only happens while the window stays valid; the moment removing s[left] would break it, left stops and right grows again.

In the .NET library

This is the hardest sliding-window shape: both edges move independently, driven by the formed == required condition rather than a fixed size or a simple threshold.