TIC
The Interns Company

Minimum Window Substring

HardAcceptance: 39.7%
Hash TableStringSliding Window

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

Constraints:

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 10^5
  • s and t consist of uppercase and lowercase English letters
  • A valid window may contain additional characters that are not in t

Input Format:

  • String s
  • String t

Output Format:

  • Return the minimum window substring of s that contains all characters in t

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 s only has one 'a', return empty string.

Solutions

Sliding Window with Hash Maps

Time: O(m + n)
Space: O(k)

Use two hash maps to track character frequencies in t and the current window, along with two pointers to identify the minimum window.

Optimized Sliding Window with Filtered Scanning

Time: O(m + n)
Space: O(k)

Optimize by only considering characters in s that are present in t, reducing unnecessary iterations.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Initialize targetMap: {A:1, B:1, C:1}, requiredChars=3
  2. Initialize left=0, right=0, windowMap={}, formedChars=0
  3. Add 'A': windowMap={A:1}, formedChars=1
  4. Add 'D': windowMap={A:1, D:1}, formedChars=1
  5. Add 'O': windowMap={A:1, D:1, O:1}, formedChars=1
  6. Add 'B': windowMap={A:1, D:1, O:1, B:1}, formedChars=2
  7. Add 'E': windowMap={A:1, D:1, O:1, B:1, E:1}, formedChars=2
  8. Add 'C': windowMap={A:1, D:1, O:1, B:1, E:1, C:1}, formedChars=3 (found all characters!)
  9. Current window is 'ADOBEC', try contracting from left
  10. Remove 'A': windowMap={A:0, D:1, O:1, B:1, E:1, C:1}, formedChars=2, window invalid
  11. Continue expanding...
  12. Add characters until we find 'BANC' at the end with all required characters
  13. After contraction, 'BANC' is the minimum valid window

Hints

Hint 1
Use a sliding window approach with two pointers to track the current window.
Hint 2
Use a hash map or array to keep track of the frequency of characters in t that we need to find.
Hint 3
Expand the right pointer until we have all required characters, then contract the left pointer to find the minimum valid window.

Video Tutorial

Minimum Window Substring - Sliding Window

YouTube•Learn the Minimum Window Substring solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the sliding window approach, expanding and contracting to find the minimum valid substring.

Key visualization elements:

  • current window
  • required characters
  • matched characters

Similar Questions

Longest Substring Without Repeating Characters

Medium

Given a string s, find the length of the longest substring without repeating characters.

Asked By

AmazonMicrosoftFacebookGoogleAppleAdobeUberLinkedIn

Implementation Notes

This is a classic sliding window problem that tests understanding of hash tables and two-pointer techniques. The optimized solution with filtering can significantly improve performance for large strings.