Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.8 kB
3
Indexable
Never
class Solution {
    public String minWindow(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        if(len1==0 || len2==0){
            return "";
        }
        int start = 0;
        int windowLength = -1;
        int end = 0;

        HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
        for(int i=0; i<len2; i++){
            char c = t.charAt(i);
            map2.put(c, map2.getOrDefault(c, 0)+1);
        }

        int required = map2.size();
        int formed = 0;
        int left = 0;

        HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();

        for(int right=0; right<len1; right++){
            char c = s.charAt(right);
            map1.put(c, map1.getOrDefault(c, 0)+1);

            if(map2.containsKey(c) && map1.get(c)==map2.get(c)){
                formed++;
            }

            while(left<=right && formed==required){
                int currMin = right - left + 1;
                if((windowLength==-1)||(windowLength>currMin)){
                    windowLength = currMin;
                    System.out.println(windowLength);
                    start = left;
                    end = right;
                }
                char leftChar = s.charAt(left);

                if(map1.containsKey(leftChar)){
                    map1.put(leftChar, map1.get(leftChar)-1);
                }

                if(map2.containsKey(leftChar) && map1.get(leftChar)<map2.get(leftChar)){
                    formed--;
                }
                
                left++;
            }
        }
        
        if(windowLength==-1){
            return "";
        }

        return s.substring(start, end+1);
    }
}