Java solution with sliding windows


  • 0
    H
    import java.util.*;
    public class Solution {
        public String minWindow(String s, String t) {
            Map<Character, Integer> dict = new HashMap<>(), has = new HashMap<>();
            for(char i:t.toCharArray()){
                if(dict.containsKey(i)) dict.put(i, dict.get(i)+1);
                else dict.put(i, 1);
                has.put(i, 0);
            }
            int left = 0, right = 0, count = 0, minlen = Integer.MAX_VALUE, lindex = -1, rindex = -1;
            char[] cha = s.toCharArray();
            while(right < s.length()){
                while(right < s.length() && count < t.length()){
                    if(dict.get(cha[right]) != null){
                        if(has.get(cha[right]) < dict.get(cha[right])) count++;
                        has.put(cha[right], has.get(cha[right])+1);
                    }
                    right++;
                }
                while(left < right && count == t.length()){
                    if(dict.get(cha[left]) != null){
                        if(has.get(cha[left]).equals(dict.get(cha[left]))) count--;
                        has.put(cha[left], has.get(cha[left])-1);
                        if(right-left < minlen && count == t.length()-1) {
                            minlen = Math.min(minlen, right-left);
                            lindex = left;
                            rindex = right;
                        }
                    }
                    left++;
                }
    
            }
            if(lindex >= 0 && rindex >=0)
            return s.substring(lindex, rindex);
            else return "";
        }
    }

Log in to reply
 

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