76. Minimum Window Substring

Problem:

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 empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

5/7/2018 update:
A more concise solution:

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0)
            return "";
        int l = 0, r = 0, start = 0, len = Integer.MAX_VALUE, count = t.length();
        int[] map = new int[256];
        for (char c: t.toCharArray()) {
            map[c]++;
        }
        
        while (r < s.length()) {
            if (map[s.charAt(r++)]-- > 0) count--;
            while (count == 0) {
                if (r - l < len) {
                    len = r - l;
                    start = l;
                }
                if (map[s.charAt(l++)]++ == 0) count++;
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

Analysis:

Sliding window problem. Similar to Minimum Size Subarray Sum. Why do we need to shrink window when found satisfying case?

If current window is  xxxxxAxxxBxxxC. It's not the optimal solution apparently. So we need to shrink window by increasing left pointer mean while updating counter. 

Solution:

The tricky part of this problem is: it asks to return the string not the length. So keep updating the start index and the length of the answer. 

class Solution {
    public String minWindow(String s, String t) {
        if(s == null || s.length() == 0)
            return "";
        int[] map = new int[256];
        for(char c: t.toCharArray()) {
            map[c]++;
        }
        int count = t.length(), l = 0, r = 0, start = 0, len = Integer.MAX_VALUE;
        while(r < s.length()) {
            // update fast pointer
            if(map[s.charAt(r++)]-- > 0) count--;
            // update window 
            while(count == 0) {
                // update res 
                String temp = s.substring(l, r);
                start = r - l < len ? l : start;
                len = Math.min(len, r - l);
                // move slow pointer
                // if meet char in t
                if (map[s.charAt(l++)]++ >= 0) count++;
            }
        }
        
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}