Minimum Window Subsequence — Solution in Python, Java & C++
Minimum Window Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Window Subsequence is a hard coding problem on strings, dynamic programming and two pointers, asked in Amazon, Google and Uber interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming, Two Pointers, Sliding Window
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Find the shortest contiguous substring of s1 that contains s2 as a subsequence.
If there is none, return the empty string. If several are equally short, return the one that starts earliest.
Example 1
Input: s1 = "codekairo", s2 = "dei"
Output: "dekai"
Explanation: The only `d` is at index 2, and the window must reach the `i` at index 6.
Example 2
Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
Explanation: "bdde" is also a window but it is longer.
Example 3
Input: s1 = "codekairo", s2 = "zz"
Output: ""
Explanation: No window contains it.
Constraints
1 <= s1.length <= 200001 <= s2.length <= 100Both strings consist of lowercase English letters.
Hints for Minimum Window Subsequence
Hint 1
A subsequence match, not a substring match — the characters of
s2need only appear in order.Hint 2
Greedily match
s2forward from a start position; the first position where the match completes is the tightest possible end.Hint 3
From that end, walk backwards matching
s2in reverse to pull the start as far right as it will go.
How to solve Minimum Window Subsequence
Two greedy passes per candidate. Going forward finds the earliest end that can complete the match; going backward from that end finds the latest start that still works. Together they produce the minimal window beginning at or after the current position.
Approach
- From
i, scan forward matching characters ofs2in order; stop when the last one is consumed, at indexk. - If the scan runs off the end, no further window exists — stop.
- From
k, scan backward matchings2in reverse; the position where the first character is consumed is the tightest startback. - Record the window and restart the outer scan at
back + 1.
Why it works
The forward scan is greedy-earliest, so no window starting at or after i can end before k. The backward scan is greedy-latest from that fixed end, so no window ending at k can start after back. Restarting at back + 1 skips only starts whose optimal window is the one just recorded, so nothing shorter is missed, and each character is visited a bounded number of times.
Complexity
- Time —
O(n · m) in the worst case - Space —
O(1) beyond the output
Pitfalls
- Treating the requirement as a substring match misses every window with characters interleaved.
- Restarting the outer scan at
i + 1instead ofback + 1is correct but slower, and restarting atk + 1skips valid windows. - Ties are broken by the earliest start, so record only on a strictly shorter window.
Reference solution
Python
def minWindow(s1: str, s2: str) -> str:
n, m = len(s1), len(s2)
best_start, best_len = -1, n + 1
i = 0
while i < n:
j, k = 0, i
while k < n:
if s1[k] == s2[j]:
j += 1
if j == m:
break
k += 1
if j < m:
break
back, jj = k, m - 1
while jj >= 0:
if s1[back] == s2[jj]:
jj -= 1
if jj >= 0:
back -= 1
if k - back + 1 < best_len:
best_len = k - back + 1
best_start = back
i = back + 1
return "" if best_start < 0 else s1[best_start:best_start + best_len]Java
public static String minWindow(String s1, String s2) {
int n = s1.length(), m = s2.length();
int bestStart = -1, bestLen = n + 1;
int i = 0;
while (i < n) {
int j = 0, k = i;
while (k < n) {
if (s1.charAt(k) == s2.charAt(j)) {
j++;
if (j == m) break;
}
k++;
}
if (j < m) break;
int back = k, jj = m - 1;
while (jj >= 0) {
if (s1.charAt(back) == s2.charAt(jj)) jj--;
if (jj >= 0) back--;
}
if (k - back + 1 < bestLen) {
bestLen = k - back + 1;
bestStart = back;
}
i = back + 1;
}
return bestStart < 0 ? "" : s1.substring(bestStart, bestStart + bestLen);
}C++
string minWindow(string s1, string s2) {
int n = (int) s1.size(), m = (int) s2.size();
int bestStart = -1, bestLen = n + 1;
int i = 0;
while (i < n) {
int j = 0, k = i;
while (k < n) {
if (s1[k] == s2[j]) {
j++;
if (j == m) break;
}
k++;
}
if (j < m) break;
int back = k, jj = m - 1;
while (jj >= 0) {
if (s1[back] == s2[jj]) jj--;
if (jj >= 0) back--;
}
if (k - back + 1 < bestLen) {
bestLen = k - back + 1;
bestStart = back;
}
i = back + 1;
}
return bestStart < 0 ? string("") : s1.substr(bestStart, bestLen);
}JavaScript
var minWindow = function(s1, s2) {
var n = s1.length, m = s2.length;
var bestStart = -1, bestLen = n + 1;
var i = 0;
while (i < n) {
var j = 0, k = i;
while (k < n) {
if (s1.charAt(k) === s2.charAt(j)) {
j++;
if (j === m) break;
}
k++;
}
if (j < m) break;
var back = k, jj = m - 1;
while (jj >= 0) {
if (s1.charAt(back) === s2.charAt(jj)) jj--;
if (jj >= 0) back--;
}
if (k - back + 1 < bestLen) { bestLen = k - back + 1; bestStart = back; }
i = back + 1;
}
return bestStart < 0 ? "" : s1.substring(bestStart, bestStart + bestLen);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming