Java solution using sliding window


  • 0
    R
    class Solution {
        
        /**
            Set - set of characters to be found
            tcmap - count of each character found in string t
            tmap - count of characters found till now in string s
            
            if(n < tn) return empty
            
            Sliding window - l,h as boundaries
            if(current size < min) {record size, boundaries;}
            
            while(i < n) {
                if c in set, 
                    increase count if (tmap(c) <= tcmap(c)) // count - 1
                    increase tmap(c)
                    if(count == 1) set lower boundary 'l'
                    if(count == tn) set higher boundary 'h'
                        if(current size < minsize) {record size, boundaries;}
                        increment 'l' till next character found
                            adjust count and tmap as a(l) is eliminated from window
            }
        */
        
        public String minWindow(String s, String t) {
            Set tset = new HashSet();
            Map<Character, Integer> tmap = new HashMap<>();
            Map<Character, Integer> tcmap = new HashMap<>();
            
            int tn = t.length(), n = s.length();
            if(n < tn) {
                return "";
            }
            
            for(int i=0;i<tn;i++) {
                char c = t.charAt(i);
                tset.add(c);
                tmap.put(c, 0);
                if(tcmap.containsKey(c)) {
                    int val = tcmap.get(c);
                    val++;
                    tcmap.put(c, val);
                } else {
                    tcmap.put(c, 1);
                }
                //System.out.println("adding - "+c+", "+tset.contains(c));
            }
            
            int l=-1, count =0, h=-1, min = Integer.MAX_VALUE;
            
            int ml = -1, mh = -1;
            
            int i=0;
            while(i<n) {
                char c = s.charAt(i);
                
                if(tset.contains(c)) {
                    //System.out.println("found - "+c);
                    int val = tmap.get(c);
                    val++;
                    //System.out.println("val - "+val+", tcmap.get(c) - "+tcmap.get(c));
                    tmap.put(c, val);
                    if(val <= tcmap.get(c)) {
                        count++;
                        if(count == 1) {
                            l = i;
                        } 
                        if(count == tn) {
                            h=i;
                            int size = h-l+1;
                            if(size < min) {
                                //System.out.println("size - "+size);
                                min = size;
                                ml = l;
                                mh = h;
                            }  
                            /** reset state to just before h, move l */
                            val--;
                            tmap.put(c, val);
                            count--;
                                
                            if(h>l) { // h & l are diffrnt
                                int lval = tmap.get(s.charAt(l));
                                lval--;
                                tmap.put(s.charAt(l), lval);
                                
                                if(lval < tcmap.get(s.charAt(l))) {
                                    count--;
                                }
                                l++;
                                while(l<i) {
                                    c = s.charAt(l);
                                    if(tset.contains(c)) {
                                        break;
                                    }
                                    l++;
                                }
                                i--;
                            }
                            /** move l */    
                            //System.out.println("l - "+l+", h-"+h);
                        }
                    }
                }
                i++;
            }
            
            if(mh<0) {
                return "";
            }
            return s.substring(ml, mh+1);
            
        }
    }```

Log in to reply
 

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