76. Minimum Window Substring

Intuition

Sliding window: expand the right edge until all required characters are covered, then shrink the left edge to minimise the window size while still covering all characters. Track "how many required characters are still unmet" as a counter to decide when the window is valid - this avoids re-scanning the frequency array on every check.

Algorithm

1Build a frequency count of t in a 128-element int array. Set required = t.Length.
2Expand right pointer: for each character s[right], decrement count[s[right]]. If it was > 0 before, decrement required.
3When required == 0 (all characters covered): record window if it is smaller than the best so far.
4Shrink left pointer: increment count[s[left]]. If it becomes > 0 again, increment required. Advance left.
5Repeat until right reaches end of s.

Example Walkthrough

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

1.Expand right until required=0: window "ADOBEC" (indices 0 - 5). Record length 6.
2.Shrink left: remove A -> required=1. Expand right to include next A.
3.Window "DOBECODEBA" - shrink left again until "BANC" (indices 9 - 12). Length 4.
4.Shrink left: remove B -> required=1. Right exhausted. Best window is "BANC".

Output: "BANC"

Common Pitfalls

•Use an int[128] character array instead of a Dictionary for O(1) per character operations.
•Decrement count BEFORE checking if it was > 0 (or check > 0 before decrement) - order matters for the required counter.
•Edge case: if t is longer than s or s is empty, return "" immediately.

76.cs

// Approach: Sliding window with a 128-slot frequency array for ASCII characters.
// 'required' tracks how many characters from t are still unmet in the current window.
// Expand right pointer: when a required character is found, decrement 'required'.
// Once required == 0 (all characters covered), try shrinking the left pointer.
// Shrink left: when removing a character from t would break coverage, stop and record window size.
// Using an int array (size 128) instead of a Dictionary gives O(1) per character vs O(1) amortised.
// Time: O(n + m) where n = |s|, m = |t|. Space: O(1) since the character set is fixed at 128.

public class Solution
{
    public string MinWindow(string s, string t)
    {
        int required = t.Length;
        int[] count = new int[128];
        int minLength = s.Length + 1;
        int leftIndex = -1;

        foreach (char c in t)
            ++count[c];

        int l = 0, r = 0;
        while (r < s.Length)
        {
            if (--count[s[r]] >= 0)
                --required;

            while (required == 0)
            {
                if (r - l + 1 < minLength)
                {
                    leftIndex = l;
                    minLength = r - l + 1;
                }

                if (++count[s[l]] > 0)
                    ++required;
                l++;
            }
            r++;
        }

        return leftIndex == -1 ? "" : s.Substring(leftIndex, minLength);
    }
}

Was this solution helpful?