76. 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.

Solution:

Using hashMap + two pointers (maintain a sliding window)

• traverse the characters in T and maintain a hashmap of <Character, count>
• right pointer traverse the whole string of s start from 0 until all the characters in T has appeared (totalcount = T.length())
  • update the minLen
• left pointer continues increasing when
  • the character is not in T
  • when the character appeared times > we want in the current substring

public class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i = 0; i < t.length(); i++){
            if(map.containsKey(t.charAt(i)) ){
                map.put(t.charAt(i), map.get(t.charAt(i)) +1);
            }else{
                map.put(t.charAt(i), 1);
            }
        }

        int left = 0;
        int cnt = 0;
        int minlen = Integer.MAX_VALUE;
        int minstart = 0;
        String res = "";

        for(int i = 0; i < s.length(); i++){
            if(!map.containsKey(s.charAt(i)) ){
                continue;
            }else{
                map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
                if(map.get(s.charAt(i)) >= 0) {
                    cnt++;
                }

                while(cnt == t.length()){
                    if(i - left + 1 < minlen){
                        //res = s.substring(left, i+1);
                        minstart = left;
                        minlen = i-left + 1;
                    }
                    if(map.containsKey(s.charAt(left)) ){
                        map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
                        if(map.get(s.charAt(left)) > 0){
                            cnt --;
                        }
                    }
                    left ++;
                }
            }
        }
        if(minlen > s.length()){
            return res;
        }
        return s.substring(minstart, minstart + minlen);
    }
}

Reference:

http://blog.csdn.net/linhuanmars/article/details/20343903