Introduction

The Minimum Window Substring problem involves finding the smallest substring that contains all characters of another string.

Given:

  • a string s
  • a string t

the task is to:

  • find the minimum substring of  s
  • containing all characters of t
  • including duplicates

If no such substring exists:

  • return empty string

This problem is one of the most important applications of:

 Sliding Window Technique

This problem helps in understanding:

  • hashing
  • frequency tracking
  • dynamic window resizing
  • substring optimization

Example

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

Output:
"BANC"

Explanation:
"BANC" contains:
A, B, C
and is the minimum valid window.

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

Output:
""

Explanation:
Required characters are not available.

Constraints

1 <= s.length, t.length <= 10^5s and t contain English letters


Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Generate all substrings
  2. Check whether substring contains all characters of t
  3. Track smallest valid substring

This approach works but checking all substrings increases time complexity.

Steps

  1. Generate all substrings.
  2. Count substring frequencies.
  3. Compare with target frequencies.
  4. If valid:
    • update minimum window
  5. Return smallest substring.

Dry Run

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

Check substrings:
"A" → invalid
"ADOBEC" → valid
Length = 6
Continue searching...
"BANC" → valid
Length = 4
Minimum window updated

Final Result:
"BANC"

Brute Force Code

Complexity Analysis

Time Complexity: O(n³)Explanation:
All substrings are generated and checked.

Space Complexity: O(n)
Explanation:
Extra hashmap is used.

Approach 2 : Optimized Solution (Sliding Window)

Explanation

The optimized solution uses the Sliding Window Technique.

The idea is:

  1. Expand window using right pointer
  2. Track character frequencies
  3. When window becomes valid:
    • shrink from left
  4. Track minimum valid window

This avoids checking all substrings repeatedly.

Steps

  1. Store target frequencies.
  2. Initialize:
    • left = 0
    • right = 0
  3. Expand window.
  4. Update matched characters.
  5. Shrink valid window.
  6. Track minimum substring.

Dry Run

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

Expand window:
"ADOBEC"
All characters found
Current length = 6
Shrink window
Continue traversal...

Window becomes:
"BANC"
Length = 4
Minimum window updated

Final Result:
"BANC"

Optimized Code


Complexity Analysis

Time Complexity: O(n)
Explanation:
Each character is visited at most twice.

Space Complexity: O(n)
Explanation:
Hashmaps store character frequencies.

Edge Cases

  1. No valid substring exists
  2. Strings contain duplicate characters
  3. Strings contain one character
  4. Entire string becomes answer
  5. Multiple valid windows exist

Why This Problem is Important

This problem helps in understanding:

  1. Sliding Window Technique
  2. Dynamic window resizing
  3. Frequency tracking
  4. Hashing
  5. Substring optimization

It is one of the most important advanced sliding window interview problems.

Real-World Applications

Sliding window concepts are used in:

  1. Search engines
  2. Text analytics
  3. Data streaming
  4. Network monitoring
  5. Real-time pattern matching

Common Mistakes

  1. Incorrect frequency tracking
  2. Forgetting duplicate counts
  3. Improper window shrinking
  4. Wrong minimum update logic

Interview Tips

Interviewers often expect:

  1. Sliding Window optimization
  2. O(n) solution explanation
  3. Proper frequency handling

Always explain why shrinking the valid window helps find the minimum substring.

Related Questions

  1. Longest Substring Without Repeating Characters
  2. Longest Repeating Character Replacement
  3. Valid Anagram
  4. Subarray Sum = K
  5. Frequency Count

Final Takeaway

The Minimum Window Substring problem is a fundamental advanced sliding window problem that teaches dynamic window resizing and frequency-tracking techniques. Understanding this problem builds a strong foundation for advanced substring optimization and interview problems.