Definition
- Need map counts how many of each character the pattern requires.
- Window map counts how many of each character the current window contains.
- Formed counter tracks how many distinct required characters have their window count at or above the needed count.
- Expand phase grows the right edge until
formed == required. - Contract phase shrinks the left edge while the window remains valid, recording the smallest window found.
- Matched-count trick gives O(1) validity checks, the same idea used in the anagram problem but extended to handle multiplicities.
The National Bank of India has a long event-code log and a checklist of required event codes with minimum counts. Rajesh extends the window to the right until every checklist item is satisfied, then trims the left as far as possible while the checklist remains complete, remembering the tightest satisfying window.
Understanding the Concepts
What is the problem?
Minimum Window Substring finds the shortest substring of a text that contains all characters of a pattern including their required multiplicities. For source "ADOBECODEBANC" and pattern "ABC", the answer is "BANC" (length 4). This is one of the hardest sliding window problems and a classic interview question.
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class MinWindowMatched {
public static String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) return "";
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
Map<Character, Integer> window = new HashMap<>();
int required = need.size(), formed = 0;
int left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;
for (int right = 0; right < s.length(); right++) {
char rc = s.charAt(right);
window.merge(rc, 1, Integer::sum);
if (need.containsKey(rc) && window.get(rc).intValue() == need.get(rc).intValue()) {
formed++;
}
while (formed == required) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
char lc = s.charAt(left);
window.merge(lc, -1, Integer::sum);
if (need.containsKey(lc) && window.get(lc) < need.get(lc)) {
formed--;
}
left++;
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}
}
Why does this matter in banking?
The incident response team at the National Bank of India has a long event-code log and a set of required codes with minimum counts that together signal a specific failure. The team wants the shortest contiguous log slice containing them all so they can zoom straight to the root cause without reading the entire log.
package com.bank.service;
import com.bank.dsa.MinWindowMatched;
public class LogAnalysisService {
public void findIncident(String log, String required) {
String window = MinWindowMatched.minWindow(log, required);
System.out.println("Shortest incident window: '" + window + "'");
}
public static void main(String[] args) {
new LogAnalysisService().findIncident("ADOBECODEBANC", "ABC");
}
}
Shortest incident window: 'BANC'
How does the formed counter provide O(1) validity?
Instead of rescanning the window each step to check whether all requirements are met, the formed counter answers in O(1). It only changes when a character crosses its required threshold on the way in or out. When adding a character whose window count just reached its need count, increment formed. When removing a character whose window count just dropped below its need count, decrement formed.
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class FormedCounterDemo {
public static void main(String[] args) {
// Pattern "AAB" needs: {A:2, B:1}
Map<Character, Integer> need = new HashMap<>();
need.put('A', 2); need.put('B', 1);
int required = need.size(); // 2 distinct chars
Map<Character, Integer> win = new HashMap<>();
int formed = 0;
// Add first A
win.merge('A', 1, Integer::sum); // A:1, need A:2 ── not yet
System.out.println("After A: formed=" + formed);
// Add second A
win.merge('A', 1, Integer::sum); // A:2, need A:2 ── formed++
if (win.get('A').intValue() == need.get('A').intValue()) formed++;
System.out.println("After AA: formed=" + formed);
// Add B
win.merge('B', 1, Integer::sum); // B:1, need B:1 ── formed++
if (win.get('B').intValue() == need.get('B').intValue()) formed++;
System.out.println("After AAB: formed=" + formed + " (required=" + required + ")");
}
}
After A: formed=0
After AA: formed=1
After AAB: formed=2 (required=2)
How does contraction work?
Once formed equals required, the window is valid. Record it if it is the smallest so far. Then remove the character at the left edge: decrement its window count. If it was a required character and its count just dropped below the needed amount, decrement formed. Advance left and repeat while formed still equals required.
package com.bank.dsa;
public class ContractionDemo {
public static void main(String[] args) {
// Simulating contraction on "ADOBECODEBANC" with pattern "ABC"
// Once formed==3, try shrinking:
// [0,5] "ADOBEC" len=6, remove A ── formed drops to 2, stop
// Later: [9,12] "BANC" len=4, remove B ── formed drops to 2, stop
// Best window: "BANC" (length 4)
System.out.println(MinWindowMatched.minWindow("ADOBECODEBANC", "ABC"));
}
}
BANC
What are the edge cases?
If the pattern is longer than the source, no valid window exists. If the pattern contains characters not in the source, no valid window exists. If the pattern has duplicates, the need map holds the required count and formed only increments at the exact threshold.
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println("'" + MinWindowMatched.minWindow("A", "AA") + "'"); // "" (need 2 A's)
System.out.println("'" + MinWindowMatched.minWindow("ABC", "D") + "'"); // "" (D not in source)
System.out.println("'" + MinWindowMatched.minWindow("A", "A") + "'"); // "A"
System.out.println("'" + MinWindowMatched.minWindow("AA", "AA") + "'"); // "AA"
}
}
''
''
'A'
'AA'
What are common mistakes?
Using a set instead of a count map fails when the pattern has duplicate characters. Comparing Integer objects with == instead of .intValue() fails for counts above 127. Forgetting to decrement formed only when the count drops strictly below the need leads to premature exit from the contraction loop.
What is the time and space complexity?
Time is O(|s| + |t|). Building the need map takes O(|t|). The sliding window processes each character at most twice: once when right adds it, once when left removes it. Space is O(|s| + |t|) for the two frequency maps.
What are common interview follow-up questions?
- How would you return all minimum windows of the same length?
- How does this differ from the fixed-size anagram sliding window?
- Can you optimize space by using a single count array with positive and negative values?
- What if the pattern allows wildcards?
Visual Overview
Source: "ADOBECODEBANC" Pattern: "ABC"
Need: {A:1, B:1, C:1} required=3
┌──────────────────────────────────────┐
│ Phase 1: EXPAND (right moves) │
│ │
│ Add chars until formed == required │
│ formed++ when window[c] == need[c] │
└──────────────────────────────────────┘
│
▼
┌──────────────────────────────────────┐
│ Phase 2: CONTRACT (left moves) │
│ │
│ Record window if smallest │
│ Remove left char │
│ formed-- when window[c] < need[c] │
│ Repeat while formed == required │
└──────────────────────────────────────┘
│
▼
Continue expanding...
Windows found:
[0,5] "ADOBEC" len=6
[9,12] "BANC" len=4 ← best
Answer: "BANC"
Key Takeaway
The Minimum Window Substring with the matched-count approach is the definitive version of the hardest classic sliding window problem. At the National Bank of India, Rajesh uses it to find the shortest contiguous log slice containing every required event code with its specified multiplicity. The algorithm builds a need map from the pattern, expands the right edge until all requirements are met, then contracts the left edge as far as possible while they remain met.
The formed counter is the mechanism that keeps each step O(1). It tracks how many distinct required characters are fully satisfied in the window and only changes when a character crosses its exact required threshold. This is the same matched-count trick used in the anagram problem but extended to handle multiplicities and a superset rather than an exact permutation.
The details that separate a correct solution from common buggy versions are: (1) using a count map, not a set, so duplicate requirements are handled; (2) incrementing formed only when the count reaches exactly the need, not on every occurrence; (3) decrementing formed only when the count falls strictly below the need; and (4) using .intValue() for Integer comparisons to avoid reference equality traps above 127.
The time complexity is O(|s| + |t|) because each character enters and leaves the window at most once, and the formed counter provides constant-time validity checks. If no valid window exists, the algorithm returns an empty string cleanly.
Remember one sentence: expand until all required characters are covered, shrink while they still are, and use the formed counter at the exact threshold for O(1) validity.
---