Minimum Window Substring

MinimumWindowSubstring.java

class Solution {
    // This approach is O(n), where n = length of string s
    // The sliding window approach uses two pointers to traverse a string in linear time. Each character is visited
    // at most twice
    // There's a method `mapHasAllChars` whose time complexity may not be intuitive, so it's worth mentioning. At most
    // each map will contain all the characters from the ascii set (0 - 255), so we know that at most we will always visit 256
    // keys every time we call this method. So note this => 
    // AS LONG AS WE KNOW THE WORST CASE FOR NUMBER OF LOOP ITERATIONS BEFOREHAND, THAT LOOP'S TIME COMPLEXITY IS CONSTANT
    public String minWindow(String s, String t) {
        //Edge Cases
        if(s == null || s.isEmpty()){
            return "";
        }
        
        if (t == null || t.isEmpty()){
            return "";
        }
        
        if(s.equals(t)){
            return s;
        }
        
        //Map to store frequency of characters in string t
        Map<Character, Integer> tFreq = new HashMap<>();
        for(char c : t.toCharArray()){
            tFreq.putIfAbsent(c, 0);
            tFreq.put(c, tFreq.get(c) + 1);
        }
        
        //Map to store frequency of characters in the sliding window
        Map<Character, Integer> charFreq = new HashMap<>();
        
        //start and end indexes for result string
        int resultStartIdx = -1;
        int resultEndIdx = -1;
        
        //start and end indexes for sliding window
        int startIdx = 0;
        int endIdx = 0;
        
        while(endIdx < s.length()) {
            char currChar = s.charAt(endIdx);
            
            //Check if current character in s is also a character in t
            if(tFreq.containsKey(currChar)){
                charFreq.putIfAbsent(currChar, 0);
                charFreq.put(currChar, charFreq.get(currChar) + 1);
            }
            
            //mapHasAllChars check if the character has the same number of keys
            //and if the frequency of keys in the window is up to the frequency in string t
            while(startIdx <= endIdx && mapHasAllChars(tFreq, charFreq)){
                //resultStartIdx == -1 means that we haven't seen any matching window before
                // (endIdx - startIdx) < (resultEndIdx - resultStartIdx) here we check if the 
                // current valid window has a smaller length than the smallest we've seen before
                if(resultStartIdx == -1 || (endIdx + 1) - startIdx < (resultEndIdx + 1 ) - resultStartIdx){
                    resultStartIdx = startIdx;
                    resultEndIdx = endIdx;
                }

                //Reduce the window
                char charToRemove = s.charAt(startIdx);
                if(charFreq.containsKey(charToRemove) && charFreq.get(charToRemove) > 1){
                    charFreq.put(charToRemove, charFreq.get(charToRemove) - 1);
                }else {
                    charFreq.remove(charToRemove);
                }
            
                startIdx++;
            }
            
            //Extend the window
            endIdx++;
        }
        
        return resultStartIdx == -1 ? "" : s.substring(resultStartIdx, resultEndIdx + 1);
    }
    
    
    private boolean mapHasAllChars(Map<Character, Integer> tFreq, Map<Character, Integer> charFreq){
        if (tFreq.size() != charFreq.size()){
            return false;
        }
        
        for(Character key : tFreq.keySet()){
            if(charFreq.get(key) < tFreq.get(key)){
                return false;
            }
        }
        
        return true;
    }
}

This is a superb explanation boss. Thank you for taking your time to explain it boss, thanks 🎉

This is a superb explanation boss. Thank you for taking your time to explain it boss, thanks 🎉

You're welcome!