Minimum Window Substring

Problem 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.

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def minWindow(s: str, t: str) -> str:
    if not s or not t:
        return ""
        
    # Initialize dictionaries
    t_count = {}
    window = {}
    for char in t:
        t_count[char] = t_count.get(char, 0) + 1
        window[char] = 0
    
    # Initialize variables
    required = len(t_count)
    formed = 0
    left = right = 0
    min_len = float('inf')
    min_window = ""
    
    while right < len(s):
        # Add one character from the right
        char = s[right]
        if char in t_count:
            window[char] += 1
            if window[char] == t_count[char]:
                formed += 1
        
        # Contract window from the left
        while formed == required and left <= right:
            # Update minimum window
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_window = s[left:right + 1]
            
            # Remove leftmost character
            char = s[left]
            if char in t_count:
                window[char] -= 1
                if window[char] < tCount[char]:
                    formed -= 1
            left += 1
        
        right += 1
    
    return min_window

Java Solution


class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) {
            return "";
        }
        
        // Initialize frequency maps
        Map tCount = new HashMap<>();
        Map window = new HashMap<>();
        for (char c : t.toCharArray()) {
            tCount.put(c, tCount.getOrDefault(c, 0) + 1);
        }
        
        // Initialize variables
        int required = tCount.size();
        int formed = 0;
        int left = 0, right = 0;
        int minLen = Integer.MAX_VALUE;
        int minLeft = 0, minRight = 0;
        
        while (right < s.length()) {
            // Add one character from the right
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);
            
            if (tCount.containsKey(c) && window.get(c).equals(tCount.get(c))) {
                formed++;
            }
            
            // Contract window from the left
            while (formed == required && left <= right) {
                // Update minimum window
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                    minRight = right;
                }
                
                // Remove leftmost character
                char leftChar = s.charAt(left);
                window.put(leftChar, window.get(leftChar) - 1);
                
                if (tCount.containsKey(leftChar) && 
                    window.get(leftChar) < tCount.get(leftChar)) {
                    formed--;
                }
                
                left++;
            }
            
            right++;
        }
        
        return minLen == Integer.MAX_VALUE ? "" : 
               s.substring(minLeft, minRight + 1);
    }
}

C++ Solution


class Solution {
public:
    string minWindow(string s, string t) {
        if (s.empty() || t.empty()) {
            return "";
        }
        
        // Initialize frequency maps
        unordered_map tCount;
        unordered_map window;
        for (char c : t) {
            tCount[c]++;
        }
        
        // Initialize variables
        int required = tCount.size();
        int formed = 0;
        int left = 0, right = 0;
        int minLen = INT_MAX;
        int minLeft = 0;
        
        while (right < s.length()) {
            // Add one character from the right
            char c = s[right];
            window[c]++;
            
            if (tCount.count(c) && window[c] == tCount[c]) {
                formed++;
            }
            
            // Contract window from the left
            while (formed == required && left <= right) {
                // Update minimum window
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                }
                
                // Remove leftmost character
                char leftChar = s[left];
                window[leftChar]--;
                
                if (tCount.count(leftChar) && 
                    window[leftChar] < tCount[leftChar]) {
                    formed--;
                }
                
                left++;
            }
            
            right++;
        }
        
        return minLen == INT_MAX ? "" : 
               s.substr(minLeft, minLen);
    }
};

JavaScript Solution


/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    if (!s || !t) {
        return "";
    }
    
    // Initialize frequency maps
    const tCount = new Map();
    const window = new Map();
    for (let char of t) {
        tCount.set(char, (tCount.get(char) || 0) + 1);
    }
    
    // Initialize variables
    const required = tCount.size;
    let formed = 0;
    let left = 0, right = 0;
    let minLen = Infinity;
    let minWindow = "";
    
    while (right < s.length) {
        // Add one character from the right
        let char = s[right];
        window.set(char, (window.get(char) || 0) + 1);
        
        if (tCount.has(char) && window.get(char) === tCount.get(char)) {
            formed++;
        }
        
        // Contract window from the left
        while (formed === required && left <= right) {
            // Update minimum window
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minWindow = s.slice(left, right + 1);
            }
            
            // Remove leftmost character
            let leftChar = s[left];
            window.set(leftChar, window.get(leftChar) - 1);
            
            if (tCount.has(leftChar) && 
                window.get(leftChar) < tCount.get(leftChar)) {
                formed--;
            }
            
            left++;
        }
        
        right++;
    }
    
    return minWindow;
};

C# Solution


public class Solution {
    public string MinWindow(string s, string t) {
        if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) {
            return "";
        }
        
        // Initialize frequency dictionaries
        Dictionary tCount = new Dictionary();
        Dictionary window = new Dictionary();
        foreach (char c in t) {
            if (!tCount.ContainsKey(c)) tCount[c] = 0;
            tCount[c]++;
        }
        
        // Initialize variables
        int required = tCount.Count;
        int formed = 0;
        int left = 0, right = 0;
        int minLen = int.MaxValue;
        int minLeft = 0, minRight = 0;
        
        while (right < s.Length) {
            // Add one character from the right
            char c = s[right];
            if (!window.ContainsKey(c)) window[c] = 0;
            window[c]++;
            
            if (tCount.ContainsKey(c) && window[c] == tCount[c]) {
                formed++;
            }
            
            // Contract window from the left
            while (formed == required && left <= right) {
                // Update minimum window
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                    minRight = right;
                }
                
                // Remove leftmost character
                char leftChar = s[left];
                window[leftChar]--;
                
                if (tCount.ContainsKey(leftChar) && 
                    window[leftChar] < tCount[leftChar]) {
                    formed--;
                }
                
                left++;
            }
            
            right++;
        }
        
        return minLen == int.MaxValue ? "" : 
               s.Substring(minLeft, minRight - minLeft + 1);
    }
}

Complexity Analysis

Time Complexity: O(|S| + |T|) where |S| and |T| are the lengths of strings s and t
Space Complexity: O(|T|) to store the character frequency maps

Solution Explanation

This solution uses the sliding window technique with two pointers:

Key concept:
- Use two pointers to maintain a window
- Track character frequencies
- Expand and contract window as needed
Algorithm steps:
- Initialize frequency maps for target string
- Expand window until valid substring found
- Contract window to minimize length
- Track minimum window seen so far

Key points:

Efficient sliding window approach
Handles duplicates correctly
Maintains minimum window size
Returns empty string if no solution