Minimum Window Substring

Question (LC.76)

Given a string S and a string T, find the minimum window in S which will contain all the characters in T.

If there is no such window in S that covers all characters in T, return the empty string "".

Example

I: S = "ADOBECODEBANC", T = "ABC"
O: "BANC"

Order doesn't matter as long as the window contains all the information.

Analysis

We need a hash map to store all characters in T and their frequency. Then scan through S to find the minimum window that contains all the characters.

Brute Force Approach

for i from 0 to len(S)
    for j from i to len(S)
        if (currentChars includes searchChars)
            break
        else
            update currentChars
            j++
    end for
    update min substring j-i+1
end for

Sliding Window Approach

for i from 0 to n-1
    while (j < n && window does not contain query)
        extend the window
        j++
    end while

    if the current window contains query
        update window depending on the size

    shrink the window
end for

Code

public String minWindow(String text, String query) {
    if (text == null || query == null || query.length() == 0) {
        return "";
    }
    int n = text.length(), m = query.length();
    Map<Character, Integer> windowMap = new HashMap<>();
    Map<Character, Integer> queryMap = new HashMap<>();
    for (int i = 0; i < m; i++) {       
        Character newChar = query.charAt(i);
        addCharToMap(queryMap, newChar);
    }
    String minSubstring = "";
    int minWindowLen = Integer.MAX_VALUE;
    int j = 0;
    for (int i = 0; i < n; i++) {
        Character newChar = text.charAt(i);
        // extend
        while (j < n && !isContained(windowMap, queryMap)) {
            addCharToMap(windowMap, text.charAt(j));
            j++;
        }
        // current window
        if (isContained(windowMap, queryMap)) {
            if (j - i < minWindowLen) {
                minWindowLen = j - i;
                minSubstring = text.substring(i, j);
            }
        }
        // shrink
        removeCharFromMap(windowMap, newChar);
    }
    return minSubstring;
}

private void addCharToMap(Map<Character, Integer> map, Character newChar) {
    if (map.containsKey(newChar)) {
        map.put(newChar, map.get(newChar) + 1);
    } else {
        map.put(newChar, 1);
    }
}

private void removeCharFromMap(Map<Character, Integer> map, Character oldChar) {
    if (map.get(oldChar) != null && map.get(oldChar) > 0) {
        map.put(oldChar, map.get(oldChar) - 1);
    }
}

private boolean isContained(Map<Character, Integer> windowMap, Map<Character, Integer> queryMap) {
    for (Character qKey : queryMap.keySet()) {
        if (windowMap.get(qKey) == null || windowMap.get(qKey) < queryMap.get(qKey)) {
            return false;
        }
    }
    return true;
}

Time & Space Complexity

Time O(n*#chars + m) Space O(n) can be optimized to O(m) by using a counter instead of calling isContained function with two maps