DSA Decoded | Day 21: Minimum Window Substring

Photo by Isaiah B on Unsplash

“This is a running series of posts, where I solve DSA problems and try to explain them as thoroughly as possible for anyone to understand. Usually I’ll be using JAVA for solving all problems”

The link to this question is provided below

[embed]Minimum Window Substring - NeetCode Leetcode 76. Minimum Window Substring Given two strings s and t, return the shortest substring of s such that…neetcode.io

Problem Statement:

Given two strings s and t, return the shortest substring of s such that every character in t, including duplicates, is present in the substring. If such a substring does not exist, return an empty string "".

You may assume that the correct output is always unique.

Example 1:

Input: s = "OUZODYXAZV", t = "XYZ"

Output: "YXAZ"

Constraints:

• 1 <= s.length <= 1000
• 1 <= t.length <= 1000
• s and t consist of uppercase and lowercase English letters.

Intuition:

We need to maintain a dynamic window whic would contain atleast all the characters of the target, i.e, the freq of the target characters must be greater than or equals in the current window counters.

We must include every character, expansion , which we check whether it contains atleast all the target character counts. If so, then we shrink by moving the left pointer forward, adn update result by keeping the shortest substring found. We keep shrinking as long as the count satisfies. Once it doesn’t, then we continue expanding again.

This continues until we reached end of string.

Solution:

class Solution {
    public String minWindow(String s, String t) {
        if(t.length() > s.length()) return "";

        Map<Character, Integer> target = new HashMap<>();
        String res = "";

        // map target counts
        for(char c : t.toCharArray())
            target.put(c, target.getOrDefault(c, 0) + 1);

        // dynamic window run
        int l=0;
        Map<Character, Integer> count = new HashMap<>();
        for(int r=0; r<s.length(); r++){
            // include rth
            char cur = s.charAt(r);
            count.put(cur, count.getOrDefault(cur, 0) + 1);

            // shrink till freq is valid
            while(l<=r && isValid(count, target)){
                res = ( res.equals("") || res.length() > (r-l+1) ) ? 
                    s.substring(l, r+1) : res; 
                char cl = s.charAt(l);
                count.put(cl, count.get(cl) - 1);
                l++;
            }
        }

        return res;
    }

    private boolean isValid(Map<Character, Integer> count, Map<Character, Integer> target){
        for(Map.Entry<Character, Integer> en : target.entrySet()){
            if( count.getOrDefault( en.getKey(), 0 ) < en.getValue() )
                return false;
        }

        return true;
    }
}

Complexity:

Time : O(n) , for every character we possibly do a max freq count.

Space : O(n) , we use hashmap.