Minimum Window Substring
Understanding the Problem
We need to find the shortest contiguous substring of s that contains every character in t, counting duplicates. If t = "AAB", the window must contain at least two 'A's and one 'B'.
Order does not matter. We are not searching for t as a subsequence in some particular arrangement, we need the right characters in the right quantities. This is a frequency-matching problem layered on top of a substring search.
Once we find a valid window, we can shrink it from the left to look for a smaller one, and once the window becomes invalid, we extend it from the right. This expand-then-shrink behavior is what a sliding window does.
Key Constraints:
mcan be up to10^5, so an O(m^2) brute force that checks every substring is around 10^10 operations and times out. We need something closer to O(m).- Characters are uppercase and lowercase English letters, so there are only 52 distinct characters. Fixed-size frequency arrays are enough.
- Duplicates in
tmatter, so we need frequency counts, not just a set of characters.
Approach 1: Brute Force
Intuition
Generate every possible substring of s, check whether it contains all the characters of t, and return the shortest valid one.
To check whether a substring contains all characters of t, compare character frequencies. Build a frequency map for t, build one for the substring, and verify that every character in t appears at least as many times in the substring. For a fixed starting index i, the first valid window found while extending rightward is the shortest one starting at i, so we can stop extending as soon as the window becomes valid.
Algorithm
- Build a frequency map for
t - For each starting index
ifrom 0 tom - 1 - For each ending index
jfromitom - 1, maintain a running frequency map ofs[i..j] - After adding
s[j], check if the current window satisfies all frequency requirements oft - If it does and the window is smaller than the best so far, update the result
- Return the smallest valid window found, or
""if none exists
Example Walkthrough
Take s = "ADOBECODEBANC", t = "ABC". The requirement is A:1, B:1, C:1. For each start index i, we extend rightward until the window holds all three, record its length, then move to the next i.
The smallest valid window is "BANC", which is returned.
Code
- Time Complexity: O(m^2 C). We have O(m^2) substrings in the worst case. For each new character added, we do an O(C) check across all 128 characters to verify the window is valid. With the break optimization, practical performance is better, but worst case remains O(m^2 C) where C = 128.
- Space Complexity: O(C). We use two frequency arrays of size 128 (the ASCII character set). This is constant space regardless of input size.
The bottleneck is that for every starting position i, we extend rightward until we find a valid window, then move to i + 1 and scan rightward again from scratch. The next approach removes that restart by reusing one window and shrinking it from the left instead.
Approach 2: Sliding Window
Intuition
Maintain a single window defined by two pointers, left and right. Extend right to include more characters until the window is valid (contains all of t). Then advance left to make the window smaller while it stays valid. Every time the window is valid, compare its length against the smallest seen so far.
Shrinking from the left is safe because once a window starting at left is valid, any longer window also starting at left cannot be shorter, so there is no reason to keep it once we have recorded its length. Advancing left is the only way to find a shorter window that ends at the same right or later.
To keep the validity check at O(1), track a counter formed: the number of distinct characters in t whose required count is currently met by the window. When formed equals the number of distinct characters in t, every requirement is satisfied. Adding or removing one character changes one frequency and at most adjusts formed by one, so we never rescan the whole map.
left and right each only move forward, so together they cross s at most twice, giving O(m) total pointer movements. The formed counter changes only when a character's window count crosses its required threshold: it increments exactly when windowCount[c] reaches tCount[c] on an add, and decrements exactly when it falls below tCount[c] on a removal. Counts above the requirement do not affect formed, which is why surplus characters (extra copies of a needed character, or characters not in t) are correctly ignored by the validity test.
Algorithm
- Build a frequency map
tCountfort. Count the number of distinct characters intasrequired - Initialize
left = 0,formed = 0, and a window frequency mapwindowCount - Expand
rightfrom 0 tom - 1: - Add
s[right]towindowCount - If
windowCount[s[right]]now equalstCount[s[right]], incrementformed - While
formed == required(window is valid): - Update the result if this window is smaller than the current best
- Remove
s[left]fromwindowCount - If
windowCount[s[left]]drops belowtCount[s[left]], decrementformed - Move
leftforward - Return the smallest window found
Example Walkthrough
Take s = "ADOBECODEBANC", t = "ABC", so required = 3 (distinct chars A, B, C). Indices: A0 D1 O2 B3 E4 C5 O6 D7 E8 B9 A10 N11 C12. Only the steps where the window becomes valid trigger shrinking.
The smallest recorded window is "BANC", which is returned. The window moved from "ADOBEC" (length 6) to "BANC" (length 4) without restarting the scan for each starting index the way the brute force does.
Code
- Time Complexity: O(m + n). Building
tCounttakes O(n). The two pointers together visit each character ofsat most twice (once whenrightexpands, once whenleftshrinks), so the main loop is O(m). Total: O(m + n). - Space Complexity: O(m + n). The hash maps store at most O(m) entries for
windowCountand O(n) entries fortCount. In practice, both are bounded by the character set size (52 or 128), but in Big-O terms with respect to input, it's O(m + n).
The sliding window is already O(m + n), so the asymptotic complexity cannot improve. When s contains many characters not in t, both pointers still step through those irrelevant positions. The next approach skips them by running the same window logic over only the characters that appear in t.
Approach 3: Optimized Sliding Window (Filtered)
Intuition
When s is much longer than t and contains many characters absent from t, the standard sliding window still steps over those positions one at a time. Pre-filter s into a list of (position, character) pairs that keep only characters appearing in t, then run the same sliding window over that list. The window boundaries in the original string come from the stored positions.
For example, with s = "XXXXAXXXXBXXXXCXXXX" and t = "ABC", the filtered list is [(4,'A'), (9,'B'), (14,'C')]. The window runs over 3 elements instead of 19.
This does not change the worst-case complexity. If every character in s appears in t, the filtered list is the same size as s. When s has many irrelevant characters, the filtered list is shorter and the window does less work.
Algorithm
- Build a frequency map
tCountfort - Create a filtered list of
(index, character)pairs froms, keeping only characters that appear int - Apply the sliding window on the filtered list:
- Expand
rightto include more entries until the window is valid - Shrink
leftwhile the window remains valid - The actual window in
sspans fromfiltered[left].indextofiltered[right].index - Return the smallest window found
Example Walkthrough
Take s = "ADOBECODEBANC", t = "ABC". Filtering keeps only A, B, and C and records their indices:
The window runs over these 6 entries instead of all 13 characters. required = 3.
The smallest span is [9,12], giving "BANC". Filtering reached the same answer while the window stepped over 6 entries rather than the full string.
Code
- Time Complexity: O(m + n). Building
tCountis O(n). Building the filtered list is O(m). The sliding window iterates over the filtered list, where each entry is visited at most twice (once byright, once byleft). The filtered list has at most m entries, so the total is still O(m + n). - Space Complexity: O(m + n). The filtered list stores at most m entries. The hash maps use O(n) for
tCountand O(n) forwindowCount(bounded by distinct characters int).
Summary
The sliding window satisfies the O(m + n) follow-up. The core idea is to expand the right boundary until the window is valid, then advance the left boundary to find the shortest valid window ending at each position. The formed counter is what makes each validity check O(1) instead of O(C). The filtered variant is the same algorithm with a preprocessing step that helps when s holds many characters not in t, though it does not change the worst case.
The pattern here, growing a window until a condition holds and then shrinking it to the minimum, applies to a range of substring problems where you need the smallest range satisfying a frequency or sum requirement.