Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Idea – 1

Say a window [0, j) of s is the minimum among all windows that starts at 0 and has all chars of t by the required counts. In the example, [0, 6) is this window. Now we try to shrink (left-to-right) this window as much as possible, when we cannot shrink it anymore i.e. shrinking one more char would drop count of some t-char too low, we have found the optimal window that ends at j-1. Now we drop one char and becomes one char short. Now we expand j rightwards to find that dropped char which would make the window contain all t-chars once more. We repeat this shrink-expand. If length of s is n and length of t is m, time complexity is O(n) and space complexity is O(m). 
[code lang="java"]
class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> tmap = new HashMap<>();
        for(int i = 0; i < t.length(); ++i)
        {
            char tc = t.charAt(i);
            tmap.put(tc, tmap.getOrDefault(tc, 0)+1);
        }
        
        int targetSize = t.length();
        
        // initialize window with at least all chars of t
        // window can have more of some t-chars than is required
        HashMap<Character, Integer> window = new HashMap<>();
        int j = 0;
        while(j < s.length() && targetSize > 0)
        {
            char sc = s.charAt(j);
            if(tmap.containsKey(sc))
            {
                if(window.getOrDefault(sc, 0) < tmap.get(sc))
                {
                    --targetSize;
                }
                
                window.put( sc, window.getOrDefault(sc, 0)+1 );
            }
            
            ++j;
        }
        
        if(targetSize > 0)
        {
            return "";
        }
        
        int i = 0;
        int minstart = i, minend = j;
        while(true)
        {
            // try shrinking window as much as possible
            Character skipped = null;
            while(i < j)
            {
                char ic = s.charAt(i);
                // either ic is not in t or window has extra so we can shrink
                if(tmap.containsKey(ic) && tmap.get(ic) < window.get(ic))
                {
                    window.put(ic, window.get(ic)-1);
                }
                else if(tmap.containsKey(ic)) // in window count of ic is at the edge
                {
                    window.put(ic, window.get(ic)-1);
                    
                    // expand should regain skipped
                    skipped = ic;
                    
                    // is this a better solution
                    if(minend-minstart+1 > j-i+1)
                    {
                        minstart = i;
                        minend = j;
                    }
                    
                    // skip and start expansion
                    ++i;
                    break;
                }
                
                ++i;
            }
            
            // all (t-)chars in window were required
            // so window is already optimal
            if(skipped == null)
            {
                break;
            }
            
            // expand until window regain skipped
            while(j < s.length() && s.charAt(j) != skipped)
            {
                if(tmap.containsKey(s.charAt(j)))
                {
                    window.put(s.charAt(j), window.get(s.charAt(j))+1);
                }
        
                ++j;
            }
            
            // could not find skipped through expansion
            if(j == s.length())
            {
                break;
            }
             
            // establish window [i, j)
            ++j;
            
            // skipped is included in the window, go to shrink
            window.put(skipped, window.get(skipped)+1);
        }
        
        return s.substring(minstart, minend);
    }
}
[code]

Leave a comment