Minimum Window Substring

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.

Analysis

• Keep a sliding window
• Update window size when all chars in t is found in s
• Keep the start index of sliding window as small as possible

Code

public class Solution {
    public String minWindow(String s, String t) {
        if (s.length()==0 || t.length()==0 || s.length()<t.length() || s==null || t==null) {return "";}

        //left: left nums of chars in t for matching
        //start: start of sliding window in S (inclusive)
        //end: end of sliding window in S (inclusive)
        int left = t.length(), start = 0, end = s.length()-1;

        //存放sliding window中，s中对应t里面有的char的index位置
        Deque<Integer> queue = new LinkedList<Integer>();

        //初始化：t里字母为key，出现次数为value
        //之后只要sliding window里出现一次，value就减1。减到0的时候代表刚好出现想要的次数。减到小于零代表已经有多余的字母在sliding window里出现。
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i=0;i<t.length();i++){
            char c= t.charAt(i);
            map.put(c,map.containsKey(c)?map.get(c)+1:1);
        }

        for (int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if (!map.containsKey(c)) continue;

            //add char index to queue
            queue.add(i);

            //update left num, >0说明得到了一个需要的char，left减一
            if (map.get(c)>0) left--;

            //update map：value-1
            map.put(c, map.get(c)-1);

            //从sliding windwo最左边看起，如果有重复的，那么减小window, 更新map
            while (map.get(s.charAt(queue.peek()))<0){
                char rep = s.charAt(queue.peek());
                queue.poll();
                map.put(rep, map.get(rep)+1);
            }

            //如果都找到了, update window size
            if (left==0){
                if (queue.peekLast()-queue.peek() < end -start){ 
                    start = queue.peek();
                    end = queue.peekLast();
                }
            }
        }
        if (left!=0) {return "";}
        else return s.substring(start, end+1);
    }
}

Note

• Map, not Map

Reference

• Leetcode: 2nd solution