Find the smallest window in a string containing all characters of another string

The problem, simply

You get a long string s and a short string t. Find the shortest piece of s, with its letters next to each other, that holds every letter of t. If t has a letter two times, the piece must have it at least two times too.

Give back that shortest piece. If no piece works, give back an empty string "".

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every starting slot. From each start, walk to the right and count what you have. Stop as soon as the list is covered, because walking further from this start only makes the window longer.

1. Count the letters of t in a small table.
2. For each start i, make a fresh copy of that table and walk j from i to the right.
3. Each letter you pass that is still needed lowers the missing count.
4. When missing hits 0, the window i..j is the shortest one starting at i. Keep it if it beats the best.

class Solution {
    public String minWindow(String s, String t) {
        int[] want = new int[128];
        for (char c : t.toCharArray()) want[c]++;
        int bestStart = 0, bestLen = Integer.MAX_VALUE;

        for (int i = 0; i < s.length(); i++) {
            int[] need = want.clone();          // a fresh list for this start
            int missing = t.length();
            for (int j = i; j < s.length(); j++) {
                char c = s.charAt(j);
                if (need[c] > 0) missing--;     // this letter was on the list
                need[c]--;
                if (missing == 0) {             // shortest window from i
                    if (j - i + 1 < bestLen) {
                        bestLen = j - i + 1;
                        bestStart = i;
                    }
                    break;
                }
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
    }
}

How long it takes: for each of the n starts we may walk to the end, so O(n^2). Extra room: the count table has one slot per possible letter (128), which does not grow with the input, so O(1).

Way 2: the clever way

Way 1 throws away its counts every time it moves the start. The rubber band keeps them. When the left hand lets go of one letter, you fix one count. You never start over.

Keep a table need: for each letter, how many more you still want. Keep one number missing: how many letters of t are not inside the band yet.

1. Fill need from t. Set missing to the length of t.
2. Move R right one slot at a time. If need for that letter is above 0, it is useful, so lower missing. Always lower need for it.
3. While missing is 0, the band holds everything. Measure it. Then move L right: raise need for the letter you let go, and if it climbs above 0, that letter is now missing again.
4. When R reaches the end, the best band you measured is the answer.

A count below 0 means you hold spares. Letters that are not in t also go below 0, and that is fine, because they never make missing change.

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (char c : t.toCharArray()) need[c]++;
        int missing = t.length();               // letters of t not in the band yet
        int left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (need[c] > 0) missing--;         // a useful letter came in
            need[c]--;

            while (missing == 0) {              // the band holds everything
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestStart = left;
                }
                char d = s.charAt(left);
                need[d]++;                      // let go of the leftmost letter
                if (need[d] > 0) missing++;     // it was not a spare
                left++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
    }
}

How long it takes: R moves n times and L moves at most n times, plus m steps to read t, so O(n + m). Extra room: one table of 128 counts, O(1).

Watch out for

• Measure the window before you let go of the left letter, not after.
• t longer than s means no answer. The code returns "" because missing never reaches 0.
• Upper and lower case are different letters. A and a live in different slots of the table.
• Return the best start and length, not the last window you saw.

What interviewers ask next

• Return only the length? Keep bestLen and skip the substring.
• What if the alphabet is huge, like any Unicode letter? Use a HashMap instead of the 128 table. The idea does not change.
• Smallest window that holds every different letter of s itself? Let t be the set of distinct letters of s and run the same band.
• Find all start points of anagrams of t in s? That band has a fixed size of t.length(), so both hands move together.
• Why is L moving inside a loop still linear? Because L only moves right and never comes back. Over the whole run it moves at most n times.

Remember this

Grown-up words: the rubber band is a sliding window, the two hands are two pointers, the list is a frequency count (a hash map or an array of counts), and missing is the number of unsatisfied characters.