Definition
- Need map counts how many of each character the target requires, built once before scanning.
- Window map counts how many of each character the current window contains.
- Formed counter tracks how many distinct required characters are fully satisfied in the window.
- Expand phase grows the right edge until
formed == required, meaning the window covers all target characters. - Contract phase shrinks the left edge as far as possible while the window still covers everything, recording the smallest valid window.
- O(n) time because each pointer traverses the string at most once and the formed counter provides O(1) validity checks.
The National Bank of India scans a long event-code log and must find the shortest slice that contains every required event code at least as many times as specified. Rajesh extends the slice to the right until it covers all required codes, then trims the left as much as possible while still covering them, remembering the tightest slice.
Understanding the Concepts
What is the problem?
Given a source string s and a target string t, find the shortest contiguous substring of s that contains all characters of t, including duplicates. If t has two A's, the window must contain at least two A's. If no such window exists, return an empty string.
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class MinimumWindowSubstring {
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();
int 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 National Bank of India's incident response team has a long event-code log and a set of required event codes that together signal a specific failure pattern. The team wants the shortest contiguous log slice containing all required codes so they can zoom straight to the root cause without reading the entire log.
package com.bank.service;
import com.bank.dsa.MinimumWindowSubstring;
public class IncidentService {
public void findNarrowestIncident(String log, String requiredCodes) {
String window = MinimumWindowSubstring.minWindow(log, requiredCodes);
System.out.println("Log: " + log);
System.out.println("Required: " + requiredCodes);
System.out.println("Narrowest slice: '" + window + "' (length " + window.length() + ")");
}
public static void main(String[] args) {
new IncidentService().findNarrowestIncident("ADOBECODEBANC", "ABC");
}
}
Log: ADOBECODEBANC
Required: ABC
Narrowest slice: 'BANC' (length 4)
How does the expand-then-shrink pattern work?
First build the need map from the target. Then scan the source from left to right. For each character added at the right edge, update the window map and check if a required character just reached its needed count. When all required characters are satisfied (formed equals required), start shrinking from the left: record the window if it is the smallest so far, remove the leftmost character, and if that drops a required character below its needed count, decrement formed.
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class ExpandShrinkDemo {
public static void main(String[] args) {
String s = "XAYBZCA";
String t = "ABC";
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
Map<Character, Integer> win = new HashMap<>();
int required = need.size(), formed = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char rc = s.charAt(right);
win.merge(rc, 1, Integer::sum);
if (need.containsKey(rc) && win.get(rc).intValue() == need.get(rc).intValue()) formed++;
if (formed == required) {
System.out.println("Valid window at [" + left + "," + right + "]: '" + s.substring(left, right + 1) + "'");
}
}
}
}
Valid window at [0,6]: 'XAYBZCA'
How does the formed counter keep it linear?
The formed counter eliminates the need to rescan the window on every step. It only changes when a character crosses its required threshold on the way in or out. Characters not in the need map are added to the window map but never affect formed. This gives O(1) validity checks per step.
package com.bank.dsa;
public class FormedCounterNote {
// Without formed counter: O(n * distinct_chars) to check validity each step
// With formed counter: O(1) per step, only updates on threshold crossings
//
// formed++ when: need.containsKey(c) && window.get(c) == need.get(c)
// formed-- when: need.containsKey(c) && window.get(c) < need.get(c)
//
// The equality check is what handles duplicate requirements correctly.
// If target needs 2 A's, formed increments only when window reaches exactly 2.
public static void main(String[] args) {
System.out.println("formed counter makes each step O(1)");
}
}
What are the edge cases?
If the target is longer than the source, no valid window exists. If the target is empty, the result is an empty string. If the target has duplicate characters, the need map holds the required count for each, and formed only increments when that exact count is reached.
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println(MinimumWindowSubstring.minWindow("A", "AA")); // "" (not enough A's)
System.out.println(MinimumWindowSubstring.minWindow("AA", "AA")); // "AA"
System.out.println(MinimumWindowSubstring.minWindow("ABC", "")); // ""
System.out.println(MinimumWindowSubstring.minWindow("A", "A")); // "A"
}
}
AA
A
What are common mistakes?
The most common mistake is using a set instead of a count map, which silently fails when the target has duplicate characters. The second mistake is incrementing formed on every occurrence rather than only when the exact threshold is crossed. The third mistake is comparing Integer objects with == instead of .intValue() or .equals().
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class CommonMistakesDemo {
// WRONG: uses == on Integer objects (fails for values > 127 due to caching)
public static boolean buggyCheck(Map<Character, Integer> win, Map<Character, Integer> need, char c) {
return win.get(c) == need.get(c); // reference comparison, not value!
}
// CORRECT: uses .intValue() or .equals()
public static boolean correctCheck(Map<Character, Integer> win, Map<Character, Integer> need, char c) {
return win.get(c).intValue() == need.get(c).intValue();
}
public static void main(String[] args) {
Map<Character, Integer> win = new HashMap<>();
Map<Character, Integer> need = new HashMap<>();
win.put('A', 200); need.put('A', 200);
System.out.println("Buggy: " + buggyCheck(win, need, 'A')); // may be false!
System.out.println("Correct: " + correctCheck(win, need, 'A')); // true
}
}
Buggy: false
Correct: true
What is the time and space complexity?
Time is O(|s| + |t|) where |s| is the source length and |t| is the target length. Building the need map takes O(|t|). The sliding window traverses the source once with each pointer, and each character enters and leaves the window at most once. Space is O(|s| + |t|) for the two frequency maps.
How is this different from the anagram sliding window?
The minimum window substring allows extra characters and variable window size. The anagram problem uses a fixed window size equal to the pattern length and requires an exact match. Both use the formed counter trick, but the minimum window expands and contracts freely while the anagram window slides by exactly one position.
What are common interview follow-up questions?
- How would you return all minimum windows, not just one?
- How would you handle the case where the target has characters not in the source?
- Can you solve this with an array instead of a HashMap for ASCII characters?
- How does this relate to the substring with concatenation of all words problem?
Visual Overview
Source: "ADOBECODEBANC" Target: "ABC"
Need map: {A:1, B:1, C:1} required = 3
Expand phase (right moves forward):
──────────────────────────────────────
right=0 'A' ── window{A:1} formed=1
right=1 'D' ── window{A:1,D:1}
right=2 'O' ── window{A:1,D:1,O:1}
right=3 'B' ── window{...,B:1} formed=2
right=4 'E' ── ...
right=5 'C' ── window{...,C:1} formed=3 ── VALID!
Contract phase (left moves forward):
──────────────────────────────────────
window [0,5]="ADOBEC" len=6 ── record
remove 'A' ── formed=2 ── stop contracting
Continue expanding...
right=9 'A' ── formed=3 ── VALID!
Contract: [5,9]="CODEB" ── skip, not valid
...
right=12 'C' ── formed=3 ── VALID!
Contract: [9,12]="BANC" len=4 ── new best!
Answer: "BANC"
Key Takeaway
The Minimum Window Substring is the hardest of the classic sliding window problems. Rajesh at the National Bank of India uses it to find the shortest contiguous log slice that contains every required event code with its required multiplicity. The algorithm builds a need map from the target, then expands the right edge until all requirements are met, and shrinks the left edge as far as possible while they remain met, recording the smallest valid window.
The formed counter is what keeps this linear. Instead of rescanning the window on every step to check coverage, the counter tracks how many distinct required characters are fully satisfied. It only changes when a character crosses its exact required threshold on the way in or out. Characters not in the need map are still tracked in the window but never affect the formed counter, which is how extra characters are tolerated.
The detail that separates a correct solution from a buggy one is duplicate handling. If the target needs two A's, formed increments only when the window's A count reaches exactly two, not on the first A. Using a set instead of a count map silently fails on targets with duplicate characters. Also, comparing Integer objects with == instead of .intValue() can fail for values above 127 due to Java's Integer caching behavior.
The time complexity is O(|s| + |t|) and each character enters and leaves the window at most once. If no valid window exists, the method returns an empty string. This problem combines expand-contract sliding window, frequency counting, and threshold tracking, making it a comprehensive test of sliding window mastery.
Remember one sentence: expand until all required characters are covered, shrink while they still are, and use the formed counter for O(1) validity checks.
---