Definition
- Minimum window substring – finds the shortest substring of a source string that contains every character of a pattern with at least the pattern's required multiplicity.
- Dual frequency maps – one map stores the pattern's requirements, another tracks counts inside the current window.
- Matched counter – counts how many distinct characters have met their required count inside the window.
- Expand-then-shrink – the right pointer expands until the window is complete, then the left pointer contracts while it remains complete.
- Complexity – O(|s| + |p|) time, O(|p|) space for the maps.
At the National Bank of India, a compliance officer must assemble a complete KYC packet from a stream of incoming documents. The packet requires specific documents in specific quantities. The officer expands the collection window until the packet is complete, then trims from the start while it stays complete, finding the shortest stretch of arrivals that forms a valid packet.
Understanding the Concepts
What is the Minimum Window Substring problem?
Given a source string s and a pattern p, find the shortest substring of s that contains every character of p including duplicates. For example, if s = "ADOBECODEBANC" and p = "ABC", the answer is "BANC" because it contains A, B, and C in just four characters.
package com.bank.core;
// s = "ADOBECODEBANC", p = "ABC"
// Window "ADOBEC" contains A,B,C but length 6
// Window "BANC" contains A,B,C and length 4 <- shortest
How do the dual frequency maps work?
You first build a need map from the pattern, counting how many of each character are required. You then maintain a window map that tracks counts of each relevant character inside the current window. A formed counter tracks how many distinct characters have fully met their requirement.
package com.bank.service;
import java.util.HashMap;
import java.util.Map;
public class MinWindowSubstring {
public String minWindow(String s, String p) {
if (s.isEmpty() || p.isEmpty()) return "";
Map<Character, Integer> need = new HashMap<>();
for (char c : p.toCharArray()) {
need.merge(c, 1, Integer::sum);
}
Map<Character, Integer> window = new HashMap<>();
int required = need.size(); // distinct chars needed
int formed = 0; // distinct chars fully satisfied
int left = 0;
int bestLen = Integer.MAX_VALUE;
int bestStart = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (need.containsKey(c)) {
window.merge(c, 1, Integer::sum);
if (window.get(c).intValue() == need.get(c).intValue()) {
formed++;
}
}
while (formed == required) {
int windowLen = right - left + 1;
if (windowLen < bestLen) {
bestLen = windowLen;
bestStart = left;
}
char leftChar = s.charAt(left);
if (need.containsKey(leftChar)) {
if (window.get(leftChar).intValue()
== need.get(leftChar).intValue()) {
formed--;
}
window.merge(leftChar, -1, Integer::sum);
}
left++;
}
}
return bestLen == Integer.MAX_VALUE
? ""
: s.substring(bestStart, bestStart + bestLen);
}
public static void main(String[] args) {
MinWindowSubstring solver = new MinWindowSubstring();
System.out.println(solver.minWindow("ADOBECODEBANC", "ABC"));
System.out.println(solver.minWindow("A", "A"));
System.out.println(solver.minWindow("A", "AA"));
}
}
BANC
A
Why does the matched counter update only on exact crossings?
The formed counter increments only when a character's window count reaches exactly its required count, not every time the count increases. Similarly, it decrements only when the count drops from the required amount to below it. This precise crossing logic avoids double-counting: if the pattern needs 2 A's and the window has 3 A's, formed was incremented once when the count reached 2, and adding a third A does not increment it again.
package com.bank.core;
// Pattern "AAB" -> need: {A:2, B:1}, required = 2 distinct chars
// Adding 'A' (count 1): 1 != 2, formed stays 0
// Adding 'A' (count 2): 2 == 2, formed becomes 1
// Adding 'A' (count 3): 3 != 2, formed stays 1 (no double increment)
// Adding 'B' (count 1): 1 == 1, formed becomes 2 -> window complete!
// Removing 'A' (count 3 to 2): 3 == 2+1? No, check: was count == need?
// Count was 3, need is 2, so 3 != 2, formed stays 2
// Removing 'A' (count 2 to 1): WAS count == need? 2 == 2 yes, formed drops to 1
What is the expand-then-shrink pattern?
The outer loop expands the right pointer one character at a time, updating the window map. Once the window is complete (formed equals required), you enter an inner shrink loop. While the window stays complete, you record its size if it is the smallest so far, then remove the leftmost character and advance left. The shrink loop exits when the window is no longer complete, and the outer loop resumes expanding.
package com.bank.core;
// Expand phase: right moves forward, adding characters
// -> window grows until all requirements met
// Shrink phase: left moves forward, removing characters
// -> window shrinks while it stays complete
// -> record smallest complete window
// Repeat until right reaches the end
What are the edge cases?
Edge cases include: pattern longer than source (impossible, return empty), pattern and source are identical (return the full string), pattern has duplicate characters, and source does not contain all pattern characters.
package com.bank.core;
// Edge case 1: p longer than s -> "" (impossible)
// Edge case 2: s == p -> return s
// Edge case 3: p = "AA", need two A's, not just one
// Edge case 4: s has no 'B' but p needs 'B' -> ""
// Edge case 5: p = "" -> "" (empty pattern)
How does this compare to the fixed-size window anagram search?
The minimum window substring uses a variable-size window because the answer can be any length, while the anagram search uses a fixed-size window equal to the pattern length. Both use frequency maps and a matched counter, but the shrink logic differs.
| Aspect | Minimum window substring | Anagram search |
|---|---|---|
| Window size | Variable (shrinks to minimum) | Fixed (equal to pattern length) |
| Goal | Shortest window containing all chars | Any window that is an exact anagram |
| Shrink trigger | When window is complete, try to shrink | Automatic: one in, one out per step |
| Count match | At least required counts | Exactly required counts |
package com.bank.core;
// Min window: at least the required counts (extra chars OK)
// Anagram: exactly the required counts (no extras)
// Both use the matched-counter technique
What about a banking use case?
At the National Bank of India, the onboarding system ingests a chronological stream of document-type codes for each customer. A valid KYC packet requires specific documents in specific quantities. The system finds the shortest stretch of the stream that contains a complete packet, pinpointing the earliest moment the customer becomes fully compliant.
package com.bank.service;
public class KYCComplianceChecker {
private final MinWindowSubstring solver = new MinWindowSubstring();
public String findEarliestCompletePacket(
String documentStream, String requiredDocs) {
String window = solver.minWindow(documentStream, requiredDocs);
if (window.isEmpty()) {
System.out.println("Incomplete KYC: missing documents");
} else {
System.out.println("Earliest complete packet: " + window);
}
return window;
}
public static void main(String[] args) {
KYCComplianceChecker checker = new KYCComplianceChecker();
// A=address proof, I=identity, P=photo, S=signature
checker.findEarliestCompletePacket("XAISPXPAI", "AIP");
}
}
Earliest complete packet: AIS
What are common mistakes?
The most common bug is updating the matched counter on every increment or decrement instead of only on the exact crossing of the required count. This causes double-counting or premature detection of a complete window. Another mistake is allocating substring copies during the shrink loop instead of tracking start and length.
package com.bank.core;
// WRONG: increment formed on every add
if (need.containsKey(c)) {
window.merge(c, 1, Integer::sum);
formed++; // BUG: increments even when count exceeds requirement
}
// CORRECT: increment only on exact crossing
if (need.containsKey(c)) {
window.merge(c, 1, Integer::sum);
if (window.get(c).intValue() == need.get(c).intValue()) {
formed++; // only when count reaches exactly the required amount
}
}
What should a senior engineer know?
A senior engineer should recognize the dual-map plus matched-counter technique as the canonical template for all "contains all required characters" window problems. For a bounded alphabet, switching both maps to int[128] arrays removes boxing overhead. Tracking the best window by start index and length avoids allocating substrings during the scan, which matters when the source is very long.
package com.bank.core;
// Senior optimizations:
// 1. int[128] arrays instead of HashMaps for ASCII
// 2. Track bestStart and bestLen, slice once at the end
// 3. Filter: only process characters that appear in the pattern
// 4. Time: O(|s| + |p|), each char added and removed once
// 5. Template reuse: same structure for at-least and exactly variants
Visual Overview
Minimum Window Substring: s = "ADOBECODEBANC", p = "ABC"
need: {A:1, B:1, C:1}, required = 3
Expand phase:
┌─────────────────────────────────────────────────┐
│ right=0: 'A' -> window{A:1}, formed=1 │
│ right=1: 'D' -> not in need, skip │
│ right=2: 'O' -> not in need, skip │
│ right=3: 'B' -> window{A:1,B:1}, formed=2 │
│ right=4: 'E' -> not in need, skip │
│ right=5: 'C' -> window{A:1,B:1,C:1}, formed=3 │
│ COMPLETE! Window: "ADOBEC" (len=6) │
└─────────────────────────────────────────────────┘
Shrink phase:
┌─────────────────────────────────────────────────┐
│ Record len=6, start=0 │
│ Remove 'A': window{A:0}, formed=2 -> stop shrink │
└─────────────────────────────────────────────────┘
Continue expanding:
┌─────────────────────────────────────────────────┐
│ right=6..9: eventually 'A' at right=10 │
│ Window becomes complete again │
│ Shrink finds "BANC" (len=4) -> new best! │
└─────────────────────────────────────────────────┘
Final answer: "BANC" (start=9, length=4)
Expand-shrink cycle:
──expand──→ ──expand──→ ──expand──→
│ │ │
▼ complete ▼ complete ▼ complete
←─shrink─← ←─shrink─← ←─shrink─←
│ │ │
record best record best record best
Key Takeaway
The minimum window substring problem asks for the shortest substring of a source string that contains every character of a pattern with at least the pattern's required counts. You solve it with a variable-size sliding window that uses dual frequency maps and a matched counter. The right pointer expands until all requirements are met, then the left pointer contracts while the window stays complete, recording the smallest satisfying window.
The matched counter is the heart of the technique. It increments only when a character's window count exactly reaches its required count, and decrements only when removing a character drops the count below the requirement. This precise crossing logic prevents double-counting and is the most common source of bugs in this problem. Off-by-one errors in the counter logic silently produce wrong answers on edge cases.
The algorithm is O(|s| + |p|) because each character is added to the window once and removed once. Tracking the best window by start index and length rather than copying substrings avoids repeated allocation during the scan. For a bounded alphabet, switching both maps to integer arrays removes boxing overhead and speeds up the hot loop.
At the National Bank of India, the onboarding compliance system used this to find the shortest stretch of a document-arrival stream that contained a complete KYC packet. Pinpointing the earliest complete moment let the system auto-approve customers immediately instead of waiting for the entire stream. The dual-map plus matched-counter template also served the team for related problems like anagram search and permutation detection, making it one of the most reused patterns in the codebase.
Remember one sentence: expand right until all characters are satisfied, then shrink left while the window stays complete, updating the matched counter only on exact crossings of the required count.
---