HARD NC#19 Blind #52 Sliding Window

76. Minimum Window Substring

📖 Problem

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.

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •String/array indexing
  • •Set/Map frequency counting
  • •Pointer movement invariants

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply Sliding Window reasoning pattern

💡 Approach

  • → Use sliding window with two hash maps
  • → Track required characters and current window counts
  • → Track how many required characters are satisfied
  • → When all satisfied, try to shrink from left
  • → Time: O(m + n), Space: O(k) where k is charset size

🧭 Prerequisites

#424 Longest Repeating Character Replacement #485 Max Consecutive Ones #567 Permutation in String

🛠️ Hints & Pitfalls

Hints

  • •Use sliding window with two hash maps
  • •Track required characters and current window counts
  • •Track how many required characters are satisfied

Common Pitfalls

  • •When all satisfied, try to shrink from left
  • •Time: O(m + n), Space: O(k) where k is charset size

🧪 Test Cases

Hidden tests on submit: 2

Test Case 1
Not run
Input:
minWindow('ADOBECODEBANC', 'ABC');
Expected:
"BANC"
Test Case 2
Not run
Input:
minWindow('a', 'a');
Expected:
"a"
Test Case 3
Not run
Input:
minWindow('a', 'aa');
Expected:
""

📝 Code Editor

📚 Reference Solution

▼

🔗 Related Problems

#3 Longest Substring Without Repeating Characters #121 Best Time to Buy and Sell Stock #209 Minimum Size Subarray Sum #424 Longest Repeating Character Replacement #485 Max Consecutive Ones
⌘K Search ⌘↩ Run ⌘S Submit