Minimum Window Substring

gistfile1.txt

public class Solution {
    public String minWindow(String S, String T) {
        // Start typing your Java solution below
        // DO NOT write main() function
        HashMap<Character, LinkedList<Integer>> hash = new HashMap<Character, LinkedList<Integer>>();
        HashSet<Character> set = new HashSet<Character>();
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        int[] num = new int[256];
        for (int i = 0; i < T.length(); i++) {
            num[T.charAt(i)]++;
            set.add(T.charAt(i));
        }
        int start = -1;
        int min = S.length() + 1;
        for (int i = 0; i < S.length(); i++) {
            if (!set.contains(S.charAt(i)))
                continue;
            if (hash.containsKey(S.charAt(i))) {
                hash.get(S.charAt(i)).add(i);
                if (num[S.charAt(i)] == 0) {
                    pq.remove(hash.get(S.charAt(i)).remove());
                } else {
                    num[S.charAt(i)]--;
                }
            } else {
                LinkedList<Integer> list = new LinkedList<Integer>();
                list.add(i);
                hash.put(S.charAt(i), list);
                num[S.charAt(i)]--;
            }
            pq.add(i);
            if (pq.size() == T.length()) {
                if (min > i - pq.peek() + 1) {
                    min = i - pq.peek() + 1;
                    start = pq.peek();
                }
            }
        }
        if (min > S.length())
            return new String();
        return S.substring(start, start + min);
    }
}