O(n) window slide method


  • 0
    M

    The idea is:

    1. find a window to meet the requirement
    2. slide the left side of the window, find out the word that makes this window doesn't contain all the words of T
    3. slide the right side of the window, looking for the wanted word
        private int minLo = 0;
        private int minHi = Integer.MAX_VALUE;
        public String minWindow(String s, String t) {
            int n = s.length();
            char[] ch = s.toCharArray();
            
            int[] cnt0 = new int[128];
            for (int i = 0; i < t.length(); ++i) {
                ++cnt0[t.charAt(i)];
            }
    
            int[] cnt1 = new int[128];
            int lo = 0, hi = 0;
            boolean winOK = false;
            
            // create a window contains all the words
            while (hi < n) {
                cnt1[ch[hi]]++; // add hi into window
                if (match(cnt0, cnt1)) {
                    winOK = true;
                    break;
                }
                hi++;
            }
            if (!winOK) return "";
            update(lo, hi);
            
            while (hi < n) {
                if (!winOK) break;          // window is not full of the charater of T
                
                char removed = '0';
                while (lo <= hi && winOK) {  // slide the window to let it lost characters of T
                    cnt1[ch[lo]]--;
                    ++lo;
                    
                    removed = ch[lo - 1];
                    if (cnt1[removed] < cnt0[removed]) winOK = false; 
                    else update(lo, hi); // update window size                
                        
                }
    
                ++hi;   // from next hi
                while (hi < n && !winOK) {      // look for the word that makes the window not match T
                    cnt1[ch[hi]]++;             // add hi into window
    
                    if (ch[hi] == removed) {
                        winOK = true;
                        update(lo, hi); // update window               
                        break;
                    }
                    ++hi;
                } 
    
            
            }
            return s.substring(minLo, minHi + 1);
        }
        
        private void update(int lo, int hi) {
            if (hi - lo < minHi - minLo) {
                minHi = hi;
                minLo = lo;
            }    
        }
    
        // cnt1 must have more counts than cnt0
        private boolean match(int[] cnt0, int[] cnt1) {
            int n = cnt0.length;
            for (int i = 0; i< n; ++i) {
                if (cnt1[i] < cnt0[i]) return false;
            }
            
            return true;
        }
    
    

Log in to reply
 

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