Minimum Window Substring

Step 1: When does a window "cover" t?

A window covers t when, for every character, it has at least as many copies as t does. Checking all characters every time would be slow, so keep two pieces of state:

• need[c]: how many more copies of c the window still needs. It starts as the count of c in t, and can go negative when the window has extras.
• missing: how many characters of t are still not covered, counting repeats. The window covers t exactly when missing == 0.

Step 2: Grow until the window covers t

Add s[right]: decrease need for it. If need was positive before, this character was still needed, so missing goes down by one. Extra copies only push need below zero and do not change missing.

Step 3: Shrink while it still covers t

While missing == 0:

• record the window if it is the shortest so far;
• remove s[left]: increase its need. If that makes need positive, a needed character just left, so missing goes up and the window no longer covers t;
• move left forward.

Step 4: Why this finds the shortest

For each right, the shrinking stops at the shortest covering window that ends there. The best of these is the overall answer.

s = "ADOBECODEBANC", t = "ABC". These are the moments when a new shortest window is found.

The answer is "BANC".

One array, need, does the work of two count maps, and missing turns the "does it cover?" test into a single comparison.

public class MinimumWindowSubstring {

    public static String minWindow(String s, String t) {
        int[] need = new int[128];            // how many more of each character the window needs
        for (char c : t.toCharArray()) {
            need[c]++;
        }
        int missing = t.length();             // characters of t not yet covered
        int left = 0;
        int bestStart = 0;
        int bestLen = Integer.MAX_VALUE;
        for (int right = 0; right < s.length(); right++) {
            if (need[s.charAt(right)]-- > 0) {
                missing--;                    // this character was still needed
            }
            while (missing == 0) {            // the window covers t: try to shrink it
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestStart = left;
                }
                if (++need[s.charAt(left)] > 0) {
                    missing++;                // removing it uncovers a needed character
                }
                left++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
    }

    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));   // BANC
        System.out.println(minWindow("a", "a"));                 // a
        System.out.println("[" + minWindow("a", "aa") + "]");    // []
    }
}

The original implementation, MinimumWindowSubstring.java, is on GitHub.

• Time: O(m + n): each character of s enters and leaves the window once, plus one pass over t.
• Space: O(1): a fixed array of 128 counts.

When the window must have exactly the letters of t and nothing else, see Permutation in String. Sliding Window Basics explains the general template.