76. Minimum Window Substring – Leetcode Solutions

June 22, 2024

Table of Contents

Description:

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.

Examples:

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 in Python:

Approach:

Character Frequency Count:
- Use a hash map to store the frequency of each character in t.
- Use another hash map to keep track of the characters in the current window of s.
Sliding Window:
- Use two pointers, left and right, to represent the current window in s.
- Expand the window by moving the right pointer to the right until the window contains all characters of t with the required frequencies.
- Once the window is valid (contains all characters of t), try to minimize the window by moving the left pointer to the right while maintaining the validity of the window.
Check Valid Window:
- To check if the current window is valid, compare the frequency of characters in the window with the frequency of characters in t.
Update Result:
- Keep track of the minimum window size and update the result whenever a smaller valid window is found.
Edge Cases:
- If t is longer than s, return an empty string since it’s impossible to have a window containing all characters of t.

Python

from collections import Counter, defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        
        # Count frequencies of characters in t
        dict_t = Counter(t)
        
        # Number of unique characters in t that need to be in the window
        required = len(dict_t)
        
        # Left and right pointers
        l, r = 0, 0
        
        # Formed is used to keep track of how many unique characters in t are present in the current window in the required frequency
        formed = 0
        
        # Dictionary to keep a count of all the unique characters in the current window
        window_counts = defaultdict(int)
        
        # (window length, left, right)
        ans = float("inf"), None, None
        
        while r < len(s):
            # Add one character from the right to the window
            character = s[r]
            window_counts[character] += 1
            
            # If the frequency of the current character added equals to the desired count in t, increment the formed count
            if character in dict_t and window_counts[character] == dict_t[character]:
                formed += 1
            
            # Try and contract the window till the point where it ceases to be 'desirable'
            while l <= r and formed == required:
                character = s[l]
                
                # Save the smallest window until now
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)
                
                # The character at the position pointed by the `left` pointer is no longer a part of the window
                window_counts[character] -= 1
                if character in dict_t and window_counts[character] < dict_t[character]:
                    formed -= 1
                
                # Move the left pointer ahead
                l += 1    
            
            # Keep expanding the window once we are done contracting
            r += 1
        
        return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]

Explanation:

Initialization:
- dict_t is a Counter for characters in t.
- required is the number of unique characters in t that need to be present in the window.
- window_counts is a default dictionary to count characters in the current window.
- ans holds the smallest window found (length, left index, right index).
Expand and Contract the Window:
- Move right to expand the window and include characters from s.
- When a valid window (containing all characters of t) is found, move left to minimize the window.
Update the Result:
- Whenever a valid window is found, update ans if the current window is smaller.

This approach ensures that we find the minimum window substring in linear time relative to the lengths of s and t, making it efficient for large inputs.

Solution in Javascript:

JavaScript

var minWindow = function(s, t) {
    if (s.length === 0 || t.length === 0) {
        return "";
    }
    
    // Dictionary which keeps a count of all the unique characters in t.
    let dictT = {};
    for (let char of t) {
        if (dictT[char]) {
            dictT[char] += 1;
        } else {
            dictT[char] = 1;
        }
    }
    
    // Number of unique characters in t, which need to be present in the desired window.
    let required = Object.keys(dictT).length;
    
    // Left and Right pointer
    let left = 0, right = 0;
    
    // Formed is used to keep track of how many unique characters in t are present in the current window in their required frequency.
    let formed = 0;
    
    // Dictionary which keeps a count of all the unique characters in the current window.
    let windowCounts = {};
    
    // (window length, left, right)
    let ans = [-1, 0, 0];
    
    while (right < s.length) {
        // Add one character from the right to the window
        let char = s[right];
        if (windowCounts[char]) {
            windowCounts[char] += 1;
        } else {
            windowCounts[char] = 1;
        }
        
        // If the frequency of the current character added equals to the desired count in t, increment the formed count.
        if (dictT[char] && windowCounts[char] === dictT[char]) {
            formed += 1;
        }
        
        // Try and contract the window till the point where it ceases to be 'desirable'.
        while (left <= right && formed === required) {
            char = s[left];
            
            // Save the smallest window until now.
            if (ans[0] === -1 || right - left + 1 < ans[0]) {
                ans = [right - left + 1, left, right];
            }
            
            // The character at the position pointed by the `left` pointer is no longer a part of the window.
            windowCounts[char] -= 1;
            if (dictT[char] && windowCounts[char] < dictT[char]) {
                formed -= 1;
            }
            
            // Move the left pointer ahead.
            left += 1;
        }
        
        // Keep expanding the window once we are done contracting.
        right += 1;
    }
    
    return ans[0] === -1 ? "" : s.slice(ans[1], ans[2] + 1);
};

Solution in Java:

Java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) {
            return "";
        }
        
        // Dictionary which keeps a count of all the unique characters in t.
        Map<Character, Integer> dictT = new HashMap<>();
        for (char c : t.toCharArray()) {
            dictT.put(c, dictT.getOrDefault(c, 0) + 1);
        }
        
        // Number of unique characters in t, which need to be present in the desired window.
        int required = dictT.size();
        
        // Left and Right pointer
        int left = 0, right = 0;
        
        // Formed is used to keep track of how many unique characters in t are present in the current window in their required frequency.
        int formed = 0;
        
        // Dictionary which keeps a count of all the unique characters in the current window.
        Map<Character, Integer> windowCounts = new HashMap<>();
        
        // Array to store the result (window length, left, right)
        int[] ans = {-1, 0, 0};
        
        while (right < s.length()) {
            // Add one character from the right to the window
            char charRight = s.charAt(right);
            windowCounts.put(charRight, windowCounts.getOrDefault(charRight, 0) + 1);
            
            // If the frequency of the current character added equals to the desired count in t, increment the formed count.
            if (dictT.containsKey(charRight) && windowCounts.get(charRight).intValue() == dictT.get(charRight).intValue()) {
                formed++;
            }
            
            // Try and contract the window till the point where it ceases to be 'desirable'.
            while (left <= right && formed == required) {
                char charLeft = s.charAt(left);
                
                // Save the smallest window until now.
                if (ans[0] == -1 || right - left + 1 < ans[0]) {
                    ans[0] = right - left + 1;
                    ans[1] = left;
                    ans[2] = right;
                }
                
                // The character at the position pointed by the `left` pointer is no longer a part of the window.
                windowCounts.put(charLeft, windowCounts.get(charLeft) - 1);
                if (dictT.containsKey(charLeft) && windowCounts.get(charLeft).intValue() < dictT.get(charLeft).intValue()) {
                    formed--;
                }
                
                // Move the left pointer ahead.
                left++;
            }
            
            // Keep expanding the window once we are done contracting.
            right++;
        }
        
        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }
}

Solution in C#:

C#

public class Solution {
    public string MinWindow(string s, string t) {
        if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) {
            return "";
        }
        
        // Dictionary which keeps a count of all the unique characters in t.
        Dictionary<char, int> dictT = new Dictionary<char, int>();
        foreach (char c in t) {
            if (dictT.ContainsKey(c)) {
                dictT[c]++;
            } else {
                dictT[c] = 1;
            }
        }
        
        // Number of unique characters in t, which need to be present in the desired window.
        int required = dictT.Count;
        
        // Left and Right pointer
        int left = 0, right = 0;
        
        // Formed is used to keep track of how many unique characters in t are present in the current window in their required frequency.
        int formed = 0;
        
        // Dictionary which keeps a count of all the unique characters in the current window.
        Dictionary<char, int> windowCounts = new Dictionary<char, int>();
        
        // Array to store the result (window length, left, right)
        int[] ans = {-1, 0, 0};
        
        while (right < s.Length) {
            // Add one character from the right to the window
            char charRight = s[right];
            if (windowCounts.ContainsKey(charRight)) {
                windowCounts[charRight]++;
            } else {
                windowCounts[charRight] = 1;
            }
            
            // If the frequency of the current character added equals to the desired count in t, increment the formed count.
            if (dictT.ContainsKey(charRight) && windowCounts[charRight] == dictT[charRight]) {
                formed++;
            }
            
            // Try and contract the window till the point where it ceases to be 'desirable'.
            while (left <= right && formed == required) {
                char charLeft = s[left];
                
                // Save the smallest window until now.
                if (ans[0] == -1 || right - left + 1 < ans[0]) {
                    ans[0] = right - left + 1;
                    ans[1] = left;
                    ans[2] = right;
                }
                
                // The character at the position pointed by the `left` pointer is no longer a part of the window.
                windowCounts[charLeft]--;
                if (dictT.ContainsKey(charLeft) && windowCounts[charLeft] < dictT[charLeft]) {
                    formed--;
                }
                
                // Move the left pointer ahead.
                left++;
            }
            
            // Keep expanding the window once we are done contracting.
            right++;
        }
        
        return ans[0] == -1 ? "" : s.Substring(ans[1], ans[2] - ans[1] + 1);
    }
}

76. Minimum Window Substring – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

The collections module in Python

219. Contains Duplicate II – Leetcode Solutions

The itertools module in Python

206. Reverse Linked List – Leetcode Solutions

38. Count and Say – Leetcode Solutions

100. Same Tree – Leetcode Solutions

How to Use Set Method in Python

76. Minimum Window Substring – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular