Simple Java Solution 2 ways using (hashmap ,two pointers) or (Array, two pointers)


  • 1
    D

    1.HashMap and two pointers
    The time is about 50ms;

    public class Solution {
        public String minWindow(String s, String t) {
            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),0);
                map.put(t.charAt(i),map.get(t.charAt(i))+1);
            }
            int left=0,right=0,count=t.length(),min=Integer.MAX_VALUE,head=0;
            while(right<s.length()){
                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--;
                }
                right++;
                while(count==0){
                    if(right-left<min) {
                        min=right-left;head=left;
                    }
                    if(map.containsKey(s.charAt(left))){
                        map.put(s.charAt(left),map.get(s.charAt(left))+1);
                        if(map.get(s.charAt(left))>=1) count++;
                    }
                    left++;
                }
            }
            return min==Integer.MAX_VALUE?"":s.substring(head,head+min);
        }
    }
    

    2.Array, two pointers
    This way decrease the time to 7ms;

    public class Solution {
        public String minWindow(String s, String t) {
            int[] count=new int[128];
            for(char r:t.toCharArray()) count[r]++;
            int head=0,min=Integer.MAX_VALUE,total=t.length();
            for(int i=0,j=0;i<s.length();i++){
                if(count[s.charAt(i)]-->0) total--;
                while(total==0){
                    if(i+1-j<min) {min=i+1-j;head=j;}
                    if(++count[s.charAt(j++)]>0) total++;
                }
            }
            return min==Integer.MAX_VALUE?"":s.substring(head,head+min);
        }
    }
    

Log in to reply
 

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