15.13 Minimum Window Subsequence
Source:
src/main/kotlin/string/sliding_window/MinimumWindowSubsequence.ktPattern: forward-backward two-pointer · Core page
The Problem
The shortest substring of s1 containing s2 as a subsequence.
- Constraints: lengths ≤ 2×10⁴.
Examples
Input: s1 = "abcdebdde", s2 = "bde" -> Output: "bcde"
Intuition — slide forward to match all of s2; shrink backward to the first match
The 15.2 two-pointer, but the “valid” test is subsequence matching — shrinking backward finds the tightest window:
if (s2.length > s1.length) return ""
var minStart = -1
var minLength = Int.MAX_VALUE
var i = 0
var j = 0
while (i < s1.length) {
if (s1[i] == s2[j]) {
j++
if (j == s2.length) {
// full match: shrink backward
var end = i
j--
while (j >= 0) {
if (s1[i] == s2[j]) j--
i--
}
i++
j = 0
if (end - i + 1 < minLength) {
minLength = end - i + 1
minStart = i
}
}
}
i++
}
return if (minStart == -1) "" else s1.substring(minStart, minStart + minLength)
Why the backward shrink? The forward pass finds some end; walking back to the first character of s2’s match gives the tightest window starting there — then i resumes just after it.
Approach 1 — Forward/backward sweep (the repo’s version, optimal)
class MinimumWindowSubsequence {
/**
* @param s1 haystack
* @param s2 needle (subsequence)
* @return shortest window or ""
*/
fun minWindow(s1: String, s2: String): String {
if (s2.length > s1.length) return ""
var minStart = -1
var minLength = Int.MAX_VALUE
var i = 0
var j = 0
while (i < s1.length) {
if (s1[i] == s2[j]) {
j++
if (j == s2.length) {
val end = i
j--
while (j >= 0) {
if (s1[i] == s2[j]) j--
i--
}
i++
j = 0
if (end - i + 1 < minLength) {
minLength = end - i + 1
minStart = i
}
}
}
i++
}
return if (minStart == -1) "" else s1.substring(minStart, minStart + minLength)
}
}
public class MinimumWindowSubsequence {
/**
* @param s1 haystack
* @param s2 needle (subsequence)
* @return shortest window or ""
*/
public String minWindow(String s1, String s2) {
if (s2.length() > s1.length()) return "";
int minStart = -1, minLength = Integer.MAX_VALUE;
int i = 0, j = 0;
while (i < s1.length()) {
if (s1.charAt(i) == s2.charAt(j)) {
j++;
if (j == s2.length()) {
int end = i;
j--;
while (j >= 0) {
if (s1.charAt(i) == s2.charAt(j)) j--;
i--;
}
i++;
j = 0;
if (end - i + 1 < minLength) {
minLength = end - i + 1;
minStart = i;
}
}
}
i++;
}
return minStart == -1 ? "" : s1.substring(minStart, minStart + minLength);
}
}
#include <string>
#include <climits>
class MinimumWindowSubsequence {
public:
/**
* @param s1 haystack
* @param s2 needle (subsequence)
* @return shortest window or ""
*/
std::string minWindow(std::string s1, std::string s2) {
if (s2.size() > s1.size()) return "";
int minStart = -1, minLength = INT_MAX;
int i = 0, j = 0;
while (i < (int)s1.size()) {
if (s1[i] == s2[j]) {
j++;
if (j == (int)s2.size()) {
int end = i;
j--;
while (j >= 0) {
if (s1[i] == s2[j]) j--;
i--;
}
i++;
j = 0;
if (end - i + 1 < minLength) {
minLength = end - i + 1;
minStart = i;
}
}
}
i++;
}
return minStart == -1 ? "" : s1.substr(minStart, minLength);
}
};
def min_window(s1: str, s2: str) -> str:
"""
@param s1: haystack
@param s2: needle (subsequence)
@return: shortest window or ""
"""
if len(s2) > len(s1):
return ""
min_start = -1
min_length = float("inf")
i = j = 0
while i < len(s1):
if s1[i] == s2[j]:
j += 1
if j == len(s2):
end = i
j -= 1
while j >= 0:
if s1[i] == s2[j]:
j -= 1
i -= 1
i += 1
j = 0
if end - i + 1 < min_length:
min_length = end - i + 1
min_start = i
i += 1
return "" if min_start == -1 else s1[min_start:min_start + min_length]
#![allow(unused)]
fn main() {
impl Solution {
/// @param s1 haystack
/// @param s2 needle (subsequence)
/// @return shortest window or ""
pub fn min_window(s1: String, s2: String) -> String {
let a: Vec<char> = s1.chars().collect();
let b: Vec<char> = s2.chars().collect();
if b.len() > a.len() { return String::new(); }
let (mut min_start, mut min_length) = (-1i32, i32::MAX);
let (mut i, mut j) = (0i32, 0i32);
while i < a.len() as i32 {
if a[i as usize] == b[j as usize] {
j += 1;
if j == b.len() as i32 {
let end = i;
j -= 1;
while j >= 0 {
if a[i as usize] == b[j as usize] { j -= 1; }
i -= 1;
}
i += 1;
j = 0;
if end - i + 1 < min_length {
min_length = end - i + 1;
min_start = i;
}
}
}
i += 1;
}
if min_start == -1 {
String::new()
} else {
a[min_start as usize..(min_start + min_length) as usize].iter().collect()
}
}
}
}Dry run
Input: s1 = "abcdebdde", s2 = "bde".
scan: b(1) -> d(4) -> e(5): full match at 5. shrink: e(5)✓ d(4)✓ b(1)✓ -> i=2. window [2,5] = "bcde" (4).
resume: b(6)? s1[6]='d'... b at 6? s1 = a b c d e b d d e: b(6) d(7) e(8): full match at 8.
shrink: e(8) d(7) b(6) -> i=7? window [7,8]? "de"? s2 needs bde — shrink walks: e(8)✓ d(7)✓ b(6)✓
-> i=6? window [6,8] = "bde" (3) — shorter! min = 3, "bde".
Hmm the expected output is "bcde" — because "bde" at [6,8]... the expected is "bcde"? Let me check:
s1 = "abcdebdde": substrings containing "bde" as subsequence: "bcde" (idx 1-4), "bdde"? (5-8)...
"bde" at [6,8]? s1[6]='d', s1[7]='d', s1[8]='e' — no 'b' at 6. s1[5]='b', s1[7]='d', s1[8]='e':
window [5,8] = "bdde" (4). So min is "bcde" (4) ✓ (my quick trace was sloppy; the algorithm's
forward-backward walk handles it correctly)
Complexity
Time. Each char visited twice:
$$ T(n, m) = O(n \cdot m) $$
Space. Constants:
$$ S(n, m) = O(1) $$
Variants & follow-ups
- Minimum Window Substring (15.2) — the frequency-window sibling.
- Interview follow-up: “Why does the backward pass give the tightest window?” It rewinds to the first character of the match, excluding everything after — the minimal start for that end. The resume
i++keeps the total scan linear.