Minimum Window Subsequence
HardUpdated: Aug 2, 2025
Practice on:
Problem
Given strings s1 and s2, return _the minimum contiguous substring part of _s1 , so thats2 is a subsequence of the part.
If there is no such window in s1 that covers all characters in s2, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.
Examples
Example 1:
Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
Explanation:
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of s2 in the window must occur in order.
Example 2:
Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
Output: ""
Constraints:
1 <= s1.length <= 2 * 10^41 <= s2.length <= 100s1ands2consist of lowercase English letters.
Solution
Method 1 – Two Pointers with Backtracking
Intuition
To find the minimum window in s1 containing s2 as a subsequence, we scan s1 to find the end of a valid window, then backtrack to find its start. By repeating this process, we can find the smallest such window efficiently.
Approach
- Use two pointers: one to scan
s1and one to scans2. - Move forward in
s1until all ofs2is matched as a subsequence. - Once matched, backtrack in
s1to find the leftmost start of the window. - Track the minimum window found and repeat until the end of
s1. - Return the smallest window or empty string if none found.
Code
C++
class Solution {
public:
string minWindow(string s1, string s2) {
int m = s1.size(), n = s2.size();
int min_len = INT_MAX, start = -1;
for (int i = 0; i < m; ++i) {
if (s1[i] != s2[0]) continue;
int j = i, k = 0;
while (j < m && k < n) {
if (s1[j] == s2[k]) ++k;
++j;
}
if (k == n) {
int end = j - 1;
k = n - 1;
j = end;
while (j >= i) {
if (s1[j] == s2[k]) {
if (--k < 0) break;
}
--j;
}
if (end - j < min_len) {
min_len = end - j;
start = j + 1;
}
}
}
return start == -1 ? "" : s1.substr(start, min_len);
}
};
Go
func MinWindow(s1, s2 string) string {
m, n := len(s1), len(s2)
minLen, start := m+1, -1
for i := 0; i < m; i++ {
if s1[i] != s2[0] {
continue
}
j, k := i, 0
for j < m && k < n {
if s1[j] == s2[k] {
k++
}
j++
}
if k == n {
end := j - 1
k = n - 1
j = end
for j >= i {
if s1[j] == s2[k] {
k--
if k < 0 {
break
}
}
j--
}
if end-j < minLen {
minLen = end - j
start = j + 1
}
}
}
if start == -1 {
return ""
}
return s1[start : start+minLen]
}
Java
class Solution {
public String minWindow(String s1, String s2) {
int m = s1.length(), n = s2.length();
int minLen = Integer.MAX_VALUE, start = -1;
for (int i = 0; i < m; i++) {
if (s1.charAt(i) != s2.charAt(0)) continue;
int j = i, k = 0;
while (j < m && k < n) {
if (s1.charAt(j) == s2.charAt(k)) k++;
j++;
}
if (k == n) {
int end = j - 1;
k = n - 1;
j = end;
while (j >= i) {
if (s1.charAt(j) == s2.charAt(k)) {
if (--k < 0) break;
}
j--;
}
if (end - j < minLen) {
minLen = end - j;
start = j + 1;
}
}
}
return start == -1 ? "" : s1.substring(start, start + minLen);
}
}
Kotlin
class Solution {
fun minWindow(s1: String, s2: String): String {
val m = s1.length
val n = s2.length
var minLen = Int.MAX_VALUE
var start = -1
for (i in 0 until m) {
if (s1[i] != s2[0]) continue
var j = i
var k = 0
while (j < m && k < n) {
if (s1[j] == s2[k]) k++
j++
}
if (k == n) {
val end = j - 1
k = n - 1
j = end
while (j >= i) {
if (s1[j] == s2[k]) {
k--
if (k < 0) break
}
j--
}
if (end - j < minLen) {
minLen = end - j
start = j + 1
}
}
}
return if (start == -1) "" else s1.substring(start, start + minLen)
}
}
Python
class Solution:
def minWindow(self, s1: str, s2: str) -> str:
m, n = len(s1), len(s2)
min_len, start = float('inf'), -1
i = 0
while i < m:
if s1[i] == s2[0]:
j, k = i, 0
while j < m and k < n:
if s1[j] == s2[k]:
k += 1
j += 1
if k == n:
end = j - 1
k = n - 1
j = end
while j >= i:
if s1[j] == s2[k]:
k -= 1
if k < 0:
break
j -= 1
if end - j < min_len:
min_len = end - j
start = j + 1
i += 1
return "" if start == -1 else s1[start:start+min_len]
Rust
impl Solution {
pub fn min_window(s1: String, s2: String) -> String {
let m = s1.len();
let n = s2.len();
let s1_bytes = s1.as_bytes();
let s2_bytes = s2.as_bytes();
let mut min_len = usize::MAX;
let mut start = None;
for i in 0..m {
if s1_bytes[i] != s2_bytes[0] {
continue;
}
let (mut j, mut k) = (i, 0);
while j < m && k < n {
if s1_bytes[j] == s2_bytes[k] {
k += 1;
}
j += 1;
}
if k == n {
let end = j - 1;
k = n - 1;
j = end;
while j >= i {
if s1_bytes[j] == s2_bytes[k] {
if k == 0 { break; }
k -= 1;
}
if j == 0 { break; }
j -= 1;
}
if end - j < min_len {
min_len = end - j;
start = Some(j + 1);
}
}
}
match start {
Some(idx) => s1[idx..idx+min_len].to_string(),
None => String::new(),
}
}
}
TypeScript
class Solution {
minWindow(s1: string, s2: string): string {
const m = s1.length, n = s2.length;
let minLen = Infinity, start = -1;
for (let i = 0; i < m; i++) {
if (s1[i] !== s2[0]) continue;
let j = i, k = 0;
while (j < m && k < n) {
if (s1[j] === s2[k]) k++;
j++;
}
if (k === n) {
const end = j - 1;
k = n - 1;
j = end;
while (j >= i) {
if (s1[j] === s2[k]) {
if (--k < 0) break;
}
j--;
}
if (end - j < minLen) {
minLen = end - j;
start = j + 1;
}
}
}
return start === -1 ? "" : s1.substring(start, start + minLen);
}
}
Complexity
- ⏰ Time complexity:
O(m * n)— For each position ins1, we may scan up to the length ofs2twice. - 🧺 Space complexity:
O(1)— Only a few variables are used for computation.