Java solution with long intuitive explanation based on 10-line template


  • 0
    S

    solve with a sliding window...

    extend right until i found my first substring.

    so i want to reduce the window by extending left, as there may be some filler at the beginning. continue to extend left until i hit a target. range here, between left and right, is the smallest possible window UP UNTIL right. if i want to find a smaller window, i need to extend right. keep extending right until i hit a target (we can ignore non-targets since they won't change our min window). now that ive seen a target, i need to try again to reduce the window by extending left. again, extend left until i hit a target but rememeber, right just found a new target. we need to determine if we can safely extend this left and thereby remove the left target. we can only remove it IF removing it still gives us a valid window. otherwise, we can't extend left (because if we did, our window is going to be invalid). therefore we need to track the count of each target in our window. if removing a target, reduces the count below the goal amount, then we
    cannot remove it, and thus cannot extend left. in summary, after right extension hits a target, we extend left as far as possible without invalidating our sliding window.

    after we extend left as far as we can, we repeat the process by extending right again until we see another target. everytime we see a target by right extension, we need to increment the window's target count.

    basically, i'm finding the smallest possible window with a left at each index. if right reaches the end of the string, i know im done. i don't need to continue extending left anymore because right hitting the end tells me that i've already tested every letter as a potential right for my min window.

    public String minWindow(String s, String t) {
        HashMap<Character, Integer> targetToCountInWindow = new HashMap<Character, Integer>();
        HashMap<Character, Integer> targetCountGoal = new HashMap<Character, Integer>();
        int left = 0;
        int right = 0;
        int minLeft = 0;
        int len = Integer.MAX_VALUE;
        
        for (int i = 0; i < t.length(); i++) {
            char currChar = t.charAt(i);
            if (targetCountGoal.containsKey(currChar)) {
                int count = targetCountGoal.get(currChar);
                targetCountGoal.put(currChar, ++count);
            } else {
                targetCountGoal.put(currChar, 1);
            }
            targetToCountInWindow.put(currChar,0); //initialize targetCountInWindow to all 0s
        }
    
        while (right < s.length()) {
            char rightChar = s.charAt(right);
            
            if (targetToCountInWindow.containsKey(rightChar)) {
                int rightCharCount = targetToCountInWindow.get(rightChar);
                targetToCountInWindow.put(rightChar, ++rightCharCount);
                if (windowHasAllTargets(targetToCountInWindow, targetCountGoal)) {
                    //start sliding left                    
                    while (left <= right) {
                        char leftChar = s.charAt(left);
                        if (targetToCountInWindow.containsKey(leftChar)) {
                            int leftCharCount = targetToCountInWindow.get(leftChar);
                            //if there's only the goal amount, then i can't extend left to remove leftChar from window
                            if (leftCharCount == (targetCountGoal.get(leftChar)).intValue()) {
                                if (right-left < len) {
                                    minLeft = left;
                                    len = right-left;
                                }
                                break;
                            }
                            targetToCountInWindow.put(leftChar, --leftCharCount);
                        }
                        left++;
                    }        
                }
            }
            right++;
        }
        
        if (len == Integer.MAX_VALUE) return "";
        
        return s.substring(minLeft, minLeft + len + 1);
    }
    
    private boolean windowHasAllTargets(HashMap<Character, Integer> targets, HashMap<Character,Integer> targetCountGoals) {
        
        Iterator<Map.Entry<Character, Integer>> iter = targets.entrySet().iterator();
        
        while(iter.hasNext()) {
            Map.Entry<Character, Integer> pair = iter.next();
            char currChar = pair.getKey();
            int count = pair.getValue();
            
            if (count < (targetCountGoals.get(currChar)).intValue()) return false;
        }
        
        return true;
    }

Log in to reply
 

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