Minimum Window Substring | Leetcode

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:

If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

---

Solution: Maintain a bag (multiset) of the characters in T. Iterate S from beginning to end. Keep a sliding window that goes from "windowStart" to the current index in S. Keep a counter for the number of remaining characters in T that we have not included in our sliding window yet. When the counter drops to zero, that means we have found a sliding window within S that contains all the characters in T.

There are some tricky things in this algorithm. First, the count of each element in the bag may become negative. For example, for a sliding window "ABBB", and T="AB", the count of B in the bag would be -2 and not 0! This means that you cannot use a real Bag data structure but you have to use a hashmap of integer to integer mapping.

Second, when we get a matching sliding window, try to collect the result immediately. But continue to shrink the sliding window from the left to the minimum length possible by advancing the windowStart pointer from the left. When you shrink the window until it no longer contains all the characters in T (remaining > 0), then stop shrinking the sliding window and continue iteration on S.

public class Solution {
    public String minWindow(String s, String t) {
        Map bag = new HashMap<>();
        for (int i = t.length() - 1; i >= 0; i--) {
            int ch = t.charAt(i);
            bag.put(ch, bag.containsKey(ch) ? bag.get(ch) + 1 : 1);
        }
        
        // Keep track of the minimum window found so far.        
        int minLength = 0;
        int minStart = 0;
        int minEnd = 0;
        int windowStart = 0;
        int remaining = t.length();

        for (int i = 0; i < s.length(); i++) {
            int ch = s.charAt(i);

            // Subtract ch from bag. Count could go negative!
            if (bag.containsKey(ch)) {
                if (bag.get(ch) > 0) remaining--;
                bag.put(ch, bag.get(ch) - 1);
            }
            
            while (remaining == 0 && windowStart <= i) {
                // Collect result if minimum.
                int len = i - windowStart + 1;
                if (minLength == 0 || len < minLength) {
                    minStart = windowStart;
                    minEnd = i;
                    minLength = len;
                }

                // Add back character if needed.
                ch = s.charAt(windowStart);
                if (bag.containsKey(ch)) {
                    if (bag.get(ch) >= 0) remaining++;
                    bag.put(ch, bag.get(ch) + 1);
                }

                // Advance windowStart pointer.
                windowStart++;
            }
        }
        
        return (minLength == 0) ? "" : s.substring(minStart, minEnd + 1);
    }
}