Minimum Window Substring
Mahabharata — Draupadi's Swayamvara — Finding the Shortest Proclamation That Names All Required Suitors
सर्वेषां नामानि यत्र वर्तन्ते लघुखण्डे। तत् खण्डं न्यूनतमं — तस्मिन् सत्यं निहितम्॥
*The shortest passage where all required names appear — that passage holds the truth.*
The Story
The great Swayamvara of Draupadi was unlike any other. Drupada, her father, had commissioned a sacred scroll from the royal chronicler listing all eligible suitors. The scroll `s` contained the names of many kings, represented as letters. The required suitors were encoded in a shorter string `t`.
But the divine priest had lost the master list and needed to find the SHORTEST section of the main scroll that contained all the required names (all characters of `t`, including duplicates). If `t = "ABC"`, the shortest section of `s` containing at least one A, one B, and one C was the answer.
"The challenge," Drupada told his mathematician Dhaumya, "is to find this minimum window efficiently."
Dhaumya understood the complexity: if `s = "ADOBECODEBANC"` and `t = "ABC"`, the answer was `"BANC"` (length 4), found at the end of the string.
"Two HashMap approach," Dhaumya announced. "First, build `need` — the frequency of each character required from `t`. Then, use a sliding window with a `have` map and a `formed` counter."
The algorithm:
**Initialization:** - `need` = frequency map of all characters in `t` - `required` = number of unique characters in `t` that must be satisfied - `formed` = how many unique characters we've currently satisfied (have count ≥ need count)
**Expand right:** - Add `s[right]` to `have` map - If `have[char] == need[char]`, increment `formed`
**Shrink left (when formed == required):** - Record the current window as a candidate (if smaller than best) - Remove `s[left]` from `have` - If `have[char] < need[char]`, decrement `formed` - Advance `left` - Continue shrinking while `formed == required`
Dhaumya traced through `s="ADOBECODEBANC"`, `t="ABC"`:
need={A:1, B:1, C:1}, required=3
- Expand until formed=3: window [0..5] = "ADOBEC". have={A:1,D:1,O:1,B:1,E:1,C:1}. formed=3. - Record "ADOBEC", len=6. - Shrink: remove A(left=0). have[A]=0 < need[A]=1 → formed=2. left=1. Stop. - Expand: right=6 (O), right=7 (D), right=8 (E), right=9 (B): have[B]=2, formed stays 2. right=10 (A): have[A]=1 == need[A]=1 → formed=3! - Record window [1..10] = "DOBECODEBA", len=10. Not better. - Shrink: remove D(left=1). have[D]=0... D not in need, formed unchanged=3. Record [2..10]="OBECODEBA", len=9. Shrink... keep shrinking. remove O, E, C: wait, C is in need! Check: have[C]=1 == need[C]=1. When we remove C, have[C]=0 < 1, formed=2. Stop. Actually the minimum shrink brings us to: after removing up to and including C at index 5, formed drops. Best window found: [3..10]... let me note that the optimal window is "BANC" [9..12].
"The final answer is `BANC`," Dhaumya confirmed after completing the traversal. "Length 4, the shortest window containing all of A, B, C."
"The key insight," Dhaumya elaborated, "is `formed`. We don't compare entire hashmaps — that would be O(alphabet) per step. Instead, `formed` is a single integer that tells us when all required characters are fully satisfied. It increments only when a character's count goes from `need-1` to `need`, and decrements only when a count drops from `need` to `need-1` during shrinking."
Draupadi's Swayamvara proceeded. The minimum section of the scroll that named all required suitors was identified. It contained Arjuna's name. The rest was destiny.
This is the advanced variable Sliding Window for finding the minimum window substring.
Dhaumya's First Instinct
Generate all substrings of `s`. For each, check if it contains all characters of `t` (using frequency maps). Return the shortest valid one. O(n² × m) time.
public String minWindowBruteForce(String s, String t) {
// Build frequency requirement
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
String result = "";
int minLen = Integer.MAX_VALUE;
int n = s.length();
for (int start = 0; start < n; start++) {
Map<Character, Integer> have = new HashMap<>();
for (int end = start; end < n; end++) {
have.merge(s.charAt(end), 1, Integer::sum);
// Check if window contains all of t
if (containsAll(have, need)) {
if (end - start + 1 < minLen) {
minLen = end - start + 1;
result = s.substring(start, end + 1);
}
break; // Can't do better from this start
}
}
}
return result;
}
private boolean containsAll(Map<Character,Integer> have, Map<Character,Integer> need) {
for (Map.Entry<Character, Integer> e : need.entrySet()) {
if (have.getOrDefault(e.getKey(), 0) < e.getValue()) return false;
}
return true;
}Dhaumya's Wisdom
public String minWindow(String s, String t) {
if (s.isEmpty() || t.isEmpty()) return "";
// Build requirement map
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
int required = need.size(); // Unique chars in t to satisfy
int formed = 0; // Unique chars currently satisfied
Map<Character, Integer> have = new HashMap<>();
int left = 0;
int minLen = Integer.MAX_VALUE;
int[] result = {-1, 0, 0}; // {length, left, right}
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
have.merge(c, 1, Integer::sum);
// Check if this char's requirement is now met
if (need.containsKey(c) && have.get(c).equals(need.get(c))) {
formed++;
}
// Shrink from left while window is valid
while (formed == required && left <= right) {
// Record if this is the smallest valid window
if (right - left + 1 < minLen) {
minLen = right - left + 1;
result[0] = minLen;
result[1] = left;
result[2] = right;
}
// Shrink: remove leftmost char
char leftChar = s.charAt(left);
have.merge(leftChar, -1, Integer::sum);
if (need.containsKey(leftChar) && have.get(leftChar) < need.get(leftChar)) {
formed--; // This required char is no longer satisfied
}
left++;
}
}
return result[0] == -1 ? "" : s.substring(result[1], result[2] + 1);
}
// Test
public static void main(String[] args) {
System.out.println(new Solution().minWindow("ADOBECODEBANC", "ABC")); // "BANC"
System.out.println(new Solution().minWindow("a", "a")); // "a"
System.out.println(new Solution().minWindow("a", "aa")); // ""
}Step-by-Step Walkthrough
s = "ADOBECODEBANC", t = "ABC"
need={A:1,B:1,C:1}, required=3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Expand phase:
right=0(A): have={A:1}, formed=1 (A met)
right=1(D): have+D, formed=1
right=2(O): have+O, formed=1
right=3(B): have+B, formed=2 (B met)
right=4(E): have+E, formed=2
right=5(C): have+C, formed=3 ← VALID WINDOW!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Shrink phase (formed==3):
Window [0..5]="ADOBEC", len=6. Record.
Remove left=0(A): have[A]=0 < need[A]=1 → formed=2. left=1. STOP.
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Continue expanding...right=6-9: expand, formed stays < 3
right=10(A): have[A]=1==need[A]=1 → formed=3! Window [1..10]
Shrink: remove D,O,B,E (not in need) then...
[1..10]="DOBECODEBA" len=10: record (worse than 6)
remove D(not in need), O, B: have[B]=1 still ≥ 1
remove E(not in need), C: have[C]=0<1 → formed=2. STOP.
Result so far: best is len=6.
Expand right=11(N): nothing
right=12(C): have[C]=1==need[C]=1 → formed=3! Window [6..12]
Shrink:
[6..12]="ODEBANC" len=7 → worse
remove O,D,E: not in need
remove B: have[B]=1≥1, no change to formed
[9..12]="BANC" len=4 → RECORD! Better!
remove B: have[B]=0<1 → formed=2. STOP.
✅ Return "BANC" (indices 9-12)Deep Insight
**Why use `formed` instead of comparing full maps?**
Comparing two hashmaps at each step would be O(|t|) per step, making the total O(n × |t|). The `formed` counter reduces this to O(1) per step: we only update `formed` when a character's count crosses its requirement threshold exactly — `need-1 → need` when expanding, `need → need-1` when shrinking.
**Why `.equals()` for Integer comparison in Java?** `have.get(c).equals(need.get(c))` instead of `==` because Java's Integer cache only guarantees `==` for values -128 to 127. For higher frequencies, `==` would fail. Always use `.equals()` for Integer comparison.
**What if t has duplicate characters? e.g., t="AAB"** - need={A:2, B:1}, required=2 (unique chars) - `formed` increments for A only when `have[A]` reaches exactly 2 (not when it's 1) - This correctly handles duplicates without any extra logic
**Edge cases:** - No valid window (t not a subset of s): return "" - t longer than s: immediately return "" - t equals s: return s
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n² × m) | O(m) | All O(n²) windows checked; each validation is O(m) |
| Optimal | O(n + m) | O(m) | n for sliding window; m for building need map |
Pattern Recognition
✅ Minimum window containing all characters of t (with duplicates) ✅ Two frequency maps: need + have ✅ formed counter for O(1) validity check ✅ Most complex sliding window: expand to make valid, shrink to minimize **LeetCode Trigger Phrases:** → "minimum window substring containing all characters" → "smallest window that includes all of t" → "at least" + every character of t
Bhagavad Gita 8.7
तस्मात्सर्वेषु कालेषु मामनुस्मर युध्य च। मय्यर्पितमनोबुद्धिर्मामेवैष्यस्यसंशयम्॥
Therefore, at all times remember Me and fight. With mind and intellect fixed on Me, you shall undoubtedly come to Me.
Connection: The minimum window substring algorithm must hold all required characters simultaneously in its 'memory' (the have map and formed counter) — like keeping awareness of the divine at all times while performing action. The window expands until all required presences (formed == required) are accounted for, then shrinks to the essential minimum. The Gita's command to 'remember Me at all times' is the window's invariant: all required elements must remain present, even as the window adjusts its boundaries.