Data Structures & Algorithms Sliding Window
💡
Exercise 45

Minimum Window Substring 30 XP Hard

LeetCode Ctrl+Enter Run Ctrl+S Save

Given strings s and t, return the minimum window substring in s that contains all characters of t (including duplicates).

s = 'ADOBECODEBANC', t = 'ABC' # Output: 'BANC' # It contains A, B, and C

This is the classic variable-size sliding window hard problem:

  • Expand right to include more characters
  • Once all chars of t are included, try shrinking from left
  • Track the minimum valid window

Use a counter for needed characters and a have/need comparison. Time: O(n).

📋 Instructions
Implement `min_window(s, t)` that returns the minimum window substring. Test with `s = 'ADOBECODEBANC'`, `t = 'ABC'`. Print the result.
Track 'need' dict from t and 'have' count. Expand right. When have == need count, try shrinking left while maintaining validity. Track min window boundaries.
🧪 Test Cases
Input
min_window('ADOBECODEBANC', 'ABC')
Expected
BANC
Test case 1
main.py
Hi! I'm Rex 👋
Output
Ready. Press ▶ Run or Ctrl+Enter.