76. Minimum Window Substring Leetcode Problem Java

Problem Statement: Given two strings s and t of lengths m and n respectively, return the minimum window substring 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.

Constraints:

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

Hint: Use HashMap with sliding window approach.

Get Soham’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

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.

Solution:

class Solution {
    public String minWindow(String s, String t) {
        if(t.length() > s.length()) return "";
        Map<Character, Integer> map = new HashMap<>();
        for(char c: t.toCharArray()) 
            map.put(c, map.getOrDefault(c, 0) + 1);
        int[] idx = {-1, -1};
        int l = 0, r = 0, len = Integer.MAX_VALUE;
        Map<Character, Integer> window = new HashMap<>();
        int need = map.size();
        int have = 0;
        while(r < s.length()){
            window.put(s.charAt(r), window.getOrDefault(s.charAt(r), 0) + 1);
            if(map.containsKey(s.charAt(r)) && map.get(s.charAt(r)) - window.get(s.charAt(r)) == 0) 
                have += 1;
            while(have == need){
                if(len > r - l + 1){
                    len = r - l + 1;
                    idx[0] = l;
                    idx[1] = r + 1;
                }
                window.put(s.charAt(l), window.get(s.charAt(l)) - 1);
                if(map.containsKey(s.charAt(l)) && map.get(s.charAt(l)) > window.get(s.charAt(l)))
                    have -= 1;
                l += 1;
            }
            r += 1;
        }
        if(idx[0] == -1) return "";
        else return s.substring(idx[0], idx[1]);
    }
}