Wednesday, February 4, 2015

Minimum Window Substring LeetCode

Idea is simple. Using a hashmap to store the number of elements in T.
Scan S by using two pointers.

public String minWindow(String S, String T) {
        if (S==null || S.length()==0) return "";
        //Put all the elements in the hashmap
        Map<Character, Integer> map = new HashMap<>();
        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);
            }
        }
       
        //Scan the String S
        int left = 0, right = 0, count = 0, minStart = 0, minLen = S.length()+1; //Initial value is larger than S
        for (; right<S.length(); right++) {
            if (map.containsKey(S.charAt(right))) {
                map.put(S.charAt(right), map.get(S.charAt(right))-1);
                if (map.get(S.charAt(right))>= 0) {
                    count++;
                }
                while (count == T.length()) {
                    if (right - left + 1 < minLen) {
                        minLen = right - left + 1;
                        minStart = left;
                    }
               
                if (map.containsKey(S.charAt(left))) {
                    map.put(S.charAt(left), map.get(S.charAt(left))+1);
                    if (map.get(S.charAt(left))>0) {
                        count--;
                    }
                }
                    left++;
                }
            }
        }
       
        //Special case: could not find the T
        if (minLen > S.length()) {
            return "";
        }
        return S.substring(minStart, minStart+minLen);
    }

No comments:

Post a Comment