I typed 64 lines Java Code to solve this problem. Is there a better solution?


  • 0
    C
    public class Solution {
    public String minWindow(String S, String T) {
        if(T.length()==0 || T.length()>S.length()) return "";
        HashMap<Character, List<Integer>> map = new HashMap<Character, List<Integer>>();
        HashMap<Character, Integer> found = new HashMap<Character, Integer>();
        for(Character c:T.toCharArray())
        {
            if(map.containsKey(c))
            {
                map.get(c).add(-1);
                found.put(c, found.get(c)+1);
            }
            else
            {
                LinkedList<Integer> list = new LinkedList<Integer>();
                list.add(-1);
                map.put(c, list);
                found.put(c, 1);
            }
        }
        boolean[] s = new boolean[S.length()];
        boolean first = true;
        int left = 0;
        String ret = "";
        for(int i=0; i<S.length(); i++)
        {
            Character c = S.charAt(i);
            if(map.containsKey(c))
            {
                if(found.containsKey(c))
                {
                    if(found.get(c)==1)
                    {
                        found.remove(c);
                    }
                    else
                    {
                        found.put(c, found.get(c)-1);
                    }
                }
                int last = map.get(c).remove(0);
                map.get(c).add(i);
                s[i] = true;
                while(s[left]==false) left++;
                if(last!=-1) s[last] = false;
                if(found.isEmpty())
                {
                    if(first)
                    {
                        ret = S.substring(left, i+1);
                        first = false;
                    }
                    if(left==last)
                    {
                        while(s[left]==false) left++;
                        if(i+1-left<ret.length())
                            ret = S.substring(left, i+1);
                    }
                }
            }
        }
        return ret;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.