Minimum Window Substring with Two Pointers — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Two Pointers and solve the Minimum Window Substring with Two Pointers problem optimally.
O(n)O(k)Problem Description
Given two strings, source and target, determine the length of the shortest contiguous substring within source that contains all characters of target with at least the same frequency. If target requires two instances of a specific character, the selected window in source must include at least two instances of that character. If no such substring exists, return 0.
The solution must efficiently scan the source string using a sliding window approach to minimize the search space. The window expands by moving the right pointer until all character requirements from target are satisfied, then contracts by moving the left pointer to find the minimal valid window. Track the minimum length encountered during this process.
Input consists of two strings: source (the haystack) and target (the needle). Output is an integer representing the length of the minimum window substring, or 0 if impossible.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Minimum Window Substring with Two Pointers"
WHY DOES IT MATTER?
The sliding window pattern is essential for problems that require finding optimal subarrays or substrings under constraints, as it transforms an exponential search space into a linear traversal, dramatically improving scalability.
OPTIMIZATION CHALLENGE
The key insight is to use two pointers to expand and contract the window while maintaining a frequency map and a counter of satisfied characters, ensuring that each character is processed only a constant number of times.
REAL-WORLD CONNECTION
Consider a real-time monitoring system that must detect the shortest period during which a set of metrics exceed thresholds; the sliding window allows the system to continuously evaluate and adjust the monitoring window without reprocessing the entire data stream.
When explaining this pattern in an interview, emphasize the invariant that the window always contains all required characters before attempting to shrink, and practice walking through a concrete example to demonstrate the pointer movements.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The Minimum Window Substring problem is a classic example of the sliding window technique, where two pointers delimit a contiguous segment of the source string that is examined for validity. A naive solution would generate all possible substrings, count character frequencies for each, and compare against the target’s frequency map, resulting in O(n^2 * k) time and O(k) space, which is infeasible for large inputs. The optimal approach maintains two frequency maps: one for the target and one for the current window. By expanding the right pointer to include characters until the window satisfies the target’s frequency requirements, and then contracting the left pointer to discard unnecessary characters while still maintaining validity, we achieve a single pass over the source string. This two-pointer strategy guarantees O(n) time because each character is visited at most twice (once by each pointer) and O(k) additional space for the frequency maps, where k is the number of distinct characters in the target.
Interview Questions on This Problem
Q1How would you modify the algorithm if the target string contains duplicate characters and you need to find the minimum window that contains at least the same number of each character?
You would still use the sliding window technique, but you must maintain a count of how many target characters are satisfied in the current window. Increment a counter each time a character’s frequency in the window reaches the required frequency in the target. Only when this counter equals the number of unique characters in the target do you consider the window valid and attempt to shrink it.
Q2In a distributed system, how could the Minimum Window Substring algorithm be adapted to process a stream of characters that arrives in chunks?
Treat each chunk as a segment of the source string and maintain the sliding window state across chunk boundaries. Keep the current window’s left pointer position and frequency map in a persistent state. As new chunks arrive, continue expanding the right pointer, updating frequencies, and shrinking from the left as needed, ensuring that the algorithm remains linear in the total number of processed characters.
Q3What is the impact on time complexity if the source string contains only lowercase English letters and the target string is very short?
The time complexity remains O(n) because the algorithm’s performance depends on the length of the source string, not the target. However, the constant factors are reduced because the frequency maps can be implemented as fixed-size arrays of length 26, leading to faster lookups and updates.
Examples
Input
source = "bbaaaccc", target = "abc"
Output
3
Explanation: The substring "abc" (indices 2-4) is the shortest window containing one 'a', one 'b', and one 'c'. Other valid windows like "baa" or "aac" are longer or invalid. Minimum length is 3.
Input
source = "adobecodebanc", target = "abc"
Output
4
Explanation: The substring "banc" (indices 9-12) is the shortest valid window. It contains 'b', 'a', and 'c'. Earlier windows like "adobec" are longer. Minimum length is 4.
Input
source = "a", target = "aa"
Output
0
Explanation: The target requires two 'a's, but the source only has one. No valid window exists, so return 0.
Input
source = "abab", target = "ab"
Output
2
Explanation: The substring "ab" (indices 0-1) is valid. The substring "ba" (indices 1-2) is also valid. Both have length 2. Minimum length is 2.
Constraints
- 1 <= source.length <= 10^5
- 1 <= target.length <= 10^5
- source and target consist of lowercase English letters
- The answer is guaranteed to be unique in terms of minimum length
Optimal Approach & Strategy
Use a sliding window with two pointers and frequency maps. Expand the right pointer to satisfy the target, then contract the left pointer to minimize the window while maintaining validity, achieving O(n) time.
Brute Force Approach
Generate every possible substring of the source string, count character frequencies for each, and compare against the target’s frequency map. This results in O(n^2 * k) time and is impractical for large inputs.
Code Solutions
/**
* @param {string} source
* @param {string} target
* @return {number}
*/
var minWindow = function(source, target) {
if (source.length === 0 || target.length === 0 || source.length < target.length) return 0;
const targetFreq = {};
for (let c of target) {
targetFreq[c] = (targetFreq[c] || 0) + 1;
}
const required = Object.keys(targetFreq).length;
let formed = 0;
const windowFreq = {};
let left = 0;
let minLen = Infinity;
let start = 0;
for (let right = 0; right < source.length; right++) {
const c = source[right];
windowFreq[c] = (windowFreq[c] || 0) + 1;
if (targetFreq.hasOwnProperty(c) && windowFreq[c] === targetFreq[c]) {
formed++;
}
while (formed === required) {
const windowSize = right - left + 1;
if (windowSize < minLen) {
minLen = windowSize;
start = left;
}
const leftChar = source[left];
windowFreq[leftChar]--;
if (targetFreq.hasOwnProperty(leftChar) && windowFreq[leftChar] < targetFreq[leftChar]) {
formed--;
}
left++;
}
}
return minLen === Infinity ? 0 : minLen;
};class Solution {
public:
int minWindow(string source, string target) {
if (source.empty() || target.empty() || source.size() < target.size()) return 0;
unordered_map<char, int> targetFreq;
for (char c : target) {
targetFreq[c]++;
}
int required = targetFreq.size();
int formed = 0;
unordered_map<char, int> windowFreq;
int left = 0;
int minLen = INT_MAX;
int start = 0;
for (int right = 0; right < source.size(); right++) {
char c = source[right];
windowFreq[c]++;
if (targetFreq.count(c) && windowFreq[c] == targetFreq[c]) {
formed++;
}
while (formed == required) {
int windowSize = right - left + 1;
if (windowSize < minLen) {
minLen = windowSize;
start = left;
}
char leftChar = source[left];
windowFreq[leftChar]--;
if (targetFreq.count(leftChar) && windowFreq[leftChar] < targetFreq[leftChar]) {
formed--;
}
left++;
}
}
return minLen == INT_MAX ? 0 : minLen;
}
};class Solution {
public int minWindow(String source, String target) {
if (source == null || target == null || source.length() < target.length()) return 0;
Map<Character, Integer> targetFreq = new HashMap<>();
for (char c : target.toCharArray()) {
targetFreq.put(c, targetFreq.getOrDefault(c, 0) + 1);
}
int required = targetFreq.size();
int formed = 0;
Map<Character, Integer> windowFreq = new HashMap<>();
int left = 0;
int minLen = Integer.MAX_VALUE;
int start = 0;
for (int right = 0; right < source.length(); right++) {
char c = source.charAt(right);
windowFreq.put(c, windowFreq.getOrDefault(c, 0) + 1);
if (targetFreq.containsKey(c) && windowFreq.get(c).equals(targetFreq.get(c))) {
formed++;
}
while (formed == required) {
int windowSize = right - left + 1;
if (windowSize < minLen) {
minLen = windowSize;
start = left;
}
char leftChar = source.charAt(left);
windowFreq.put(leftChar, windowFreq.get(leftChar) - 1);
if (targetFreq.containsKey(leftChar) && windowFreq.get(leftChar) < targetFreq.get(leftChar)) {
formed--;
}
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}class Solution:
def minWindow(self, source: str, target: str) -> int:
if not source or not target or len(source) < len(target):
return 0
from collections import Counter
target_freq = Counter(target)
required = len(target_freq)
formed = 0
window_freq = {}
left = 0
min_len = float('inf')
start = 0
for right in range(len(source)):
c = source[right]
window_freq[c] = window_freq.get(c, 0) + 1
if c in target_freq and window_freq[c] == target_freq[c]:
formed += 1
while formed == required:
window_size = right - left + 1
if window_size < min_len:
min_len = window_size
start = left
left_char = source[left]
window_freq[left_char] -= 1
if left_char in target_freq and window_freq[left_char] < target_freq[left_char]:
formed -= 1
left += 1
return 0 if min_len == float('inf') else min_len/**
* @param {string} source
* @param {string} target
* @return {number}
*/
var minWindow = function(source, target) {
if (source.length === 0 || target.length === 0 || source.length < target.length) return 0;
const targetFreq = {};
for (let c of target) {
targetFreq[c] = (targetFreq[c] || 0) + 1;
}
const required = Object.keys(targetFreq).length;
let formed = 0;
const windowFreq = {};
let left = 0;
let minLen = Infinity;
let start = 0;
for (let right = 0; right < source.length; right++) {
const c = source[right];
windowFreq[c] = (windowFreq[c] || 0) + 1;
if (targetFreq.hasOwnProperty(c) && windowFreq[c] === targetFreq[c]) {
formed++;
}
while (formed === required) {
const windowSize = right - left + 1;
if (windowSize < minLen) {
minLen = windowSize;
start = left;
}
const leftChar = source[left];
windowFreq[leftChar]--;
if (targetFreq.hasOwnProperty(leftChar) && windowFreq[leftChar] < targetFreq[leftChar]) {
formed--;
}
left++;
}
}
return minLen === Infinity ? 0 : minLen;
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.