Leetcode 76. Minimum Window Substring

Very High Frequency

Clarification

Okay, first I’ll restate the problem to make sure I understand it correctly. We are given two strings, s and t. We need to return the shortest substring of s that contains all characters from t, including duplicates.

Example.

Should I return the substring itself, not the length?
If no valid answer exists, should I return an empty string?
Can s and t be empty? Can t be longer than s?
What characters do they contain?

Brute-force Approach

The brute force way is to check every substring of s, count its characters, and see whether it covers t. But that would be very expensive, roughly O(n²) substrings, and checking each one costs O(n) time, so the time complexity would be $O(n^3)$.

Optimized Approach

Since this is a substring problem, we can consider to use sliding window approach trying to optimize it.

What I’ll do is that, first keep a hash map to store the required characters and their amounts of t. I believe we can optimize the hash map into a bucket array because of the limited characters, but I'll save it later when I start to code. I'll maintain a window [left, right]. Expand the right pointer until the window becomes valid, then shrink the left pointer as much as possible while keeping it valid. To check whether the window is valid or not, I'll need a variable count to store how many characters of t has been included in the window. Therefore, if count is equal to the length of t, the window should be valid.

So why does it work? There are three most important things for a sliding window: when to increase the window; when to shrink the window; when to update the result. When the window is invalid, the only way to make it valid is to increase the window to let more characters in so that the window may include all characters of t. While we increase the window, required and count has been updated correspondingly. We can think of required like a chart that shows us what characters need and their amounts to form a valid answer. Whenever we add a new character, we have to decrease its require by one. And if that character is in t, which can be captured by looking into the required array to see if it has a positive value, we need to increase count by one to show that our window gets a character of t. Once it's valid, expanding further only makes the window larger, so the best thing to do is shrink the left boundary as much as possible while keeping the window valid. And then we update the result. This guarantees that for every right pointer, we find the minimum valid window. We also need to update required and count to keep the information correct by doing the reverse things that we did when increasing the window.

Since both pointers only move forward and never backward, each character enters and leaves the window at most once, this gives us O(n) time. The buildDictionary function cost O(m) time. So the time complexity is O(m + n). The extra space we used is the required array which contains m elements. So the space complexity is O(m).

Code

class Solution {
    public String minWindow(String s, String t) {
        int left = 0, right = 0;
        int[] required = buildDictionary(t);
        int count = 0;      // how many characters of t inculded in the window
        int l = 0, r = Integer.MAX_VALUE;

        while (right < s.length()) {
            char cr = s.charAt(right);
            if (required[cr] > 0)   count++;
            required[cr]--;
            right++;

            while (left < right && isValidSubstring(count, t.length())) {
                if (r - l > right - left) {
                    r = right;
                    l = left;
                }

                char cl = s.charAt(left);
                if (required[cl] == 0)   count--;
                required[cl]++;
                left++;
            }
        }

        return r == Integer.MAX_VALUE ? "" : s.substring(l, r);
    }

    private int[] buildDictionary(String t) {
        int[] required = new int[128];

        for (char c : t.toCharArray()) {
            required[c]++;
        }

        return required;
    }

    private boolean isValidSubstring(int count, int length) {
        return count == length;
    }
}

Follow-up