LeetCode 76. Minimum Window Substring

Question

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of uppercase and lowercase English letters.

Source: https://leetcode.com/problems/minimum-window-substring/

Solution

We first expand the right end of the window to find a valid window. Then we shrink the left end to find a candidate min window.

// sliding window, Time complexity O(s.length() + t.length())
public String minWindow(String s, String t) {
    int tLen = t.length();
    int sLen = s.length();
    int minWindowLen = sLen + 1;
    // two ends of the window with min length, both inclusive
    int minWindowLeft = 0, minWindowRight = 0;
    int left = 0, right = 0;

    // the dictionary that describes characters to be included in desired window
    Map<Character, Integer> dict = new HashMap<>();
    Map<Character, Integer> wordCount = new HashMap<>();
    for (int i = 0; i < tLen; i++) {
        char c = t.charAt(i);
        dict.put(c, dict.getOrDefault(c, 0) + 1);
    }
    // number of requirements to meet
    int toMeet = dict.size();
    while (left < sLen && right < sLen) {
        char c = s.charAt(right);
        if (dict.containsKey(c)) {
            wordCount.put(c, wordCount.getOrDefault(c, 0) + 1);
            if (wordCount.get(c).intValue() == dict.get(c).intValue()) {
                toMeet--;
            }
            // valid window
            while (toMeet == 0) {
                // check and record current min window
                if (right - left + 1 < minWindowLen) {
                    minWindowLen = right - left + 1;
                    minWindowLeft = left;
                    minWindowRight = right;
                }
                // shrink window
                char cRemove = s.charAt(left);
                if (dict.containsKey(cRemove)) {
                    wordCount.put(cRemove, wordCount.get(cRemove) - 1);
                    if (wordCount.get(cRemove) < dict.get(cRemove)) {
                        toMeet++;
                    }
                }
                left++;
            }
        }
        // invalid window, expand right end
        right++;
    }
    return minWindowLen == sLen + 1 ? "" : s.substring(minWindowLeft, minWindowRight + 1);
}