How to Solve Minimum Window Substring

This problem requires efficiently tracking character counts while expanding and contracting a sliding window over s to cover all characters from t. Maintaining a hashmap of required counts and a dynamic window lets you detect when all characters are included. Two pointers iterate through s while updating the window state, ensuring the smallest valid substring is returned without redundant scanning, making the approach highly efficient for larger inputs.

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

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.

How GhostInterview Helps

• Capture the input strings s and t visually, ensuring correct character counts before starting the window algorithm.
• Trace the sliding window movement and hashmap updates, providing step-by-step answer paths with time O(m+n) and space O(|Σ|) explanation.
• Support live screen-share to highlight the current window and hashmaps, letting you verify expansions, contractions, and final substring selection.

Topic Pages

• Hash Table
• String
• Sliding Window

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.