#76

Hard

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Minimum Window Substring

Find the smallest substring of s containing all characters from t using a sliding window with running state updates for exact matches.

hash table string sliding window

Problem Statement

Given strings s and t, find the minimum window in s which contains all characters from t including duplicates. The window must cover every character from t, and if no such window exists, return an empty string. Use a sliding window approach to dynamically expand and contract over s while checking the current coverage of t's characters, ensuring the final answer is the smallest possible substring.

You must handle cases where characters repeat and where s is shorter than t. For example, in s = "ADOBECODEBANC" and t = "ABC", the correct minimum window is "BANC". This problem is ideal for the sliding window with running state updates pattern, emphasizing how to maintain a hashmap of counts and adjust the window efficiently to avoid missing or extra characters.

Examples

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2

Input: s = "a", t = "a"

Output: "a"

The entire string s is the minimum window.

Example 3

Input: s = "a", t = "aa"

Output: ""

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 <= 105
s and t consist of uppercase and lowercase English letters.

Solution Approach

Sliding Window Expansion and Hash Tracking

Initialize two pointers, left and right, to define the current window in s. Use a hashmap to store the count of characters required from t. Expand the right pointer, updating the hashmap counts for each character. Only when the current window covers all characters with correct counts, consider contracting from the left. This ensures you track the exact minimum window while efficiently skipping irrelevant characters, directly applying the sliding window with running state updates pattern.

Contracting the Window for Minimal Substring

Once the window includes all characters from t, move the left pointer forward to remove unnecessary characters. Reduce counts in the hashmap accordingly and check if the window still satisfies all requirements. If yes, continue contracting to shrink the substring. This step is crucial to avoid oversized windows and ensures the algorithm returns the smallest valid substring, reflecting the key failure mode where failing to contract could return incorrect or larger substrings.

Maintaining Character Counts and Window Validation

Maintain two hashmaps: one for characters required by t and another for the current window in s. Compare counts to validate whether the window meets all character requirements. Each move of the right or left pointer triggers updates, ensuring accurate coverage without rescanning s. This approach prevents miscounting repeated characters and leverages the sliding window with running state updates, balancing efficiency and correctness for long strings with overlapping characters.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(m + n) where m and n are the lengths of s and t, as each character is visited at most twice during expansion and contraction. Space complexity is O(|Σ|) for hashmaps storing counts of characters, proportional to the unique letters in t. This matches the provided complexity estimates for the sliding window with running state updates approach.

What Interviewers Usually Probe

Do you correctly expand and contract the window without rescanning characters?
Can you handle repeated characters in t when updating the hashmap counts?
Will you return the empty string when no valid window exists instead of partial matches?

Common Pitfalls or Variants

Common pitfalls

Failing to account for duplicate characters in t, which can result in windows that appear valid but are missing counts.
Not contracting the window from the left, returning a larger substring instead of the minimum window.
Using inefficient nested loops, leading to O(m*n) behavior instead of the linear sliding window approach.

Follow-up variants

Return the length of the minimum window substring instead of the substring itself.
Find the minimum window containing all distinct characters of t ignoring duplicates.
Determine the minimum window substring in s that covers a subset of t's characters under a given frequency threshold.

FAQ

What is the key pattern used in Minimum Window Substring?

The main pattern is sliding window with running state updates, where two pointers dynamically expand and contract the window while maintaining a character count hashmap.

How do duplicate characters in t affect the solution?

Duplicates require the window to include all instances of a character. Hashmaps track counts to ensure the current window meets the exact requirement, preventing invalid or partial matches.

What happens if s is shorter than t?

If s cannot cover all characters from t, the algorithm immediately returns an empty string, as no valid window exists.

Can the solution handle both uppercase and lowercase letters?

Yes, the solution tracks counts of each character distinctly, ensuring correct inclusion regardless of case sensitivity in s and t.

How does the sliding window maintain minimal length?

By contracting from the left whenever the window satisfies all character requirements, the algorithm continuously minimizes the substring, avoiding oversized windows and ensuring the smallest valid result.

terminal

Solution

Solution 1: Counting + Two Pointers

We use a hash table or array $\textit{need}$ to count the occurrences of each character in string $t$, and another hash table or array $\textit{window}$ to count the occurrences of each character in the sliding window. Additionally, we define two pointers $l$ and $r$ to point to the left and right boundaries of the window, a variable $\textit{cnt}$ to represent how many characters from $t$ are already included in the window, and variables $k$ and $\textit{mi}$ to represent the starting position and length of the minimum window substring.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        window = Counter()
        cnt = l = 0
        k, mi = -1, inf
        for r, c in enumerate(s):
            window[c] += 1
            if need[c] >= window[c]:
                cnt += 1
            while cnt == len(t):
                if r - l + 1 < mi:
                    mi = r - l + 1
                    k = l
                if need[s[l]] >= window[s[l]]:
                    cnt -= 1
                window[s[l]] -= 1
                l += 1
        return "" if k < 0 else s[k : k + mi]

Continue Practicing

#30 substring with concatenation of all words #3 longest substring without repeating characters #187 repeated dna sequences