5. Minimum Window Substring

Description

Given two strings s and t of lengths m and n respectively, return the minimum windowsubstring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Example 1:
Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

Example 2:
Input: s = “a”, t = “a”
Output: “a”
Explanation: The entire string s is the minimum window.

Example 3:
Input: s = “a”, t = “aa”
Output: ""
Explanation: Both ‘a’s from t must be included in the window.
Since the largest window of s only has one ‘a’, return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s and t consist of uppercase and lowercase English letters.

Approach

• One frequency map to store the frequency of second string and will decrease in second loop and check for 0 in the count telling us both string have same frequency for the character
• We maintain match to see if all the frequencies match
• min to maintain the minimum length and subStr to store the starting index of the minimum found so that way if we do sum of both we will get the end index of the solution

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> freq = new HashMap<>();
        int left = 0, min = s.length() + 1;
        int match = 0, subStr = 0;
 
        for (int i = 0; i < t.length(); i++)
            freq.put(t.charAt(i), freq.getOrDefault(t.charAt(i), 0) + 1);
 
        for (int right = 0; right < s.length(); right++) {
            char curr = s.charAt(right);
            if (freq.containsKey(curr)) {
                freq.put(curr, freq.get(curr) - 1);
                if (freq.get(curr) == 0)
                    match++;
            }
 
            while (match == freq.size()) {
                if (min > right - left + 1) {
                    min = right - left + 1;
                    subStr = left;
                }
                char delete = s.charAt(left++);
                if (freq.containsKey(delete)) {
                    if (freq.get(delete) == 0)
                        match--;
                    freq.put(delete, freq.get(delete) + 1);
                }
            }
        }
 
        return min > s.length() ? "" : s.substring(subStr, subStr + min);
    }
}