Write a program to find the smallest window that contains all characters of string itself

The problem, simply

You get a string, like aabcbcdbca. First find which different letters it uses. Here that is a, b, c and d, so k = 4 kinds.

Find the shortest piece of the string, letters next to each other, that contains at least one of every kind. If several pieces tie, give back the first one.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every starting spot, and from there grow to the right until all kinds are collected.

1. Count the kinds k in the whole string.
2. For each start i, walk j to the right and put letters in a set.
3. As soon as the set has k kinds, the piece s[i..j] is the shortest one that starts at i. Compare it with the best and move to the next start.

class Solution {
    public String smallestWindow(String s) {
        int n = s.length();
        Set<Character> all = new HashSet<>();
        for (char c : s.toCharArray()) all.add(c);
        int kinds = all.size();                             // how many different letters
        int bestStart = 0, bestLen = n;
        for (int i = 0; i < n; i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = i; j < n; j++) {
                seen.add(s.charAt(j));
                if (seen.size() == kinds) {                 // all kinds collected
                    if (j - i + 1 < bestLen) {
                        bestLen = j - i + 1;
                        bestStart = i;
                    }
                    break;                                  // longer pieces from i cannot be better
                }
            }
        }
        return s.substring(bestStart, bestStart + bestLen);
    }
}

How long it takes: n starts, and each may walk to the end, O(n^2). Extra room: a set of at most k kinds, O(k).

Way 2: the clever way

Starts that are next to each other share most of their work. A sliding window reuses it.

1. Count the kinds k. Keep a count for every letter inside the window, and have, the number of kinds whose count is at least one.
2. Move right one step at a time and add its letter. If that letter's count goes from 0 to 1, have grows.
3. While have == k, the window is good. Record it if it is the shortest so far. Then drop the letter at left and move left one step. If its count falls to 0, have shrinks and the inner loop stops.
4. When right has passed the end, the best window is the answer.

class Solution {
    public String smallestWindow(String s) {
        int n = s.length();
        if (n == 0) return "";
        boolean[] exists = new boolean[256];
        int kinds = 0;
        for (char c : s.toCharArray()) {
            if (!exists[c]) { exists[c] = true; kinds++; }   // count the kinds once
        }

        int[] count = new int[256];      // letters inside the window
        int have = 0;                    // kinds with count at least 1
        int bestStart = 0, bestLen = Integer.MAX_VALUE;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (count[s.charAt(right)]++ == 0) have++;       // a new kind came in
            while (have == kinds) {                          // the window is good
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestStart = left;
                }
                if (--count[s.charAt(left)] == 0) have--;    // drop from the back
                left++;
            }
        }
        return s.substring(bestStart, bestStart + bestLen);
    }
}

How long it takes: right visits each letter once and left visits each letter at most once, so O(n). Extra room: the count table, O(k) kinds (a fixed 256 here, which is O(1) for plain text).

Watch out for

• Recording the window after shrinking instead of before. Record while it is still good, then drop the left letter.
• Using if instead of while for the shrinking. One step of shrinking is not enough when many extra letters sit at the back.
• Upper and lower case are different letters unless the problem says otherwise.
• A string with one kind, or one letter. The answer is a single letter, and the code above handles it.

What interviewers ask next

• Smallest window that contains all letters of another string t, with repeats (LeetCode 76). Same window, but need[c] comes from t, and a kind is satisfied when count[c] reaches need[c].
• Longest window with at most k kinds (LeetCode 340). Flip the loop: grow on the right, and shrink while there are more than k kinds.
• Longest piece with no repeated letter (LeetCode 3). Same idea, shrink while the new letter's count is above one.
• Why is it O(n) even with a loop inside a loop? left only moves forward, so the inner loop runs at most n times in total.

Remember this

Grown-up words: the stretchy magnifying glass is a sliding window with two pointers, the sticker counts are a frequency table (hash map), and have is the number of satisfied distinct characters.