Minimum Window Subsequence
Problem
Given strings s1 and s2, return the minimum-length contiguous substring W of s1 such that s2 is a subsequence of W. If no such window exists, return the empty string; on ties return the leftmost answer.
s1="abcdebdde", s2="bde""bcde"def minWindow(s1, s2):
n, m = len(s1), len(s2)
best, blen = -1, n + 1
i = 0
while i < n:
j = 0
k = i
while k < n:
if s1[k] == s2[j]:
j += 1
if j == m: break
k += 1
if j < m: break
end = k
j = m - 1
while j >= 0:
if s1[k] == s2[j]: j -= 1
k -= 1
k += 1
if end - k + 1 < blen:
blen = end - k + 1; best = k
i = k + 1
return "" if best < 0 else s1[best:best + blen]function minWindow(s1, s2) {
const n = s1.length, m = s2.length;
let best = -1, blen = n + 1, i = 0;
while (i < n) {
let j = 0, k = i;
while (k < n) {
if (s1[k] === s2[j]) { j++; if (j === m) break; }
k++;
}
if (j < m) break;
const end = k;
j = m - 1;
while (j >= 0) { if (s1[k] === s2[j]) j--; k--; }
k++;
if (end - k + 1 < blen) { blen = end - k + 1; best = k; }
i = k + 1;
}
return best < 0 ? "" : s1.substring(best, best + blen);
}class Solution {
public String minWindow(String s1, String s2) {
int n = s1.length(), m = s2.length(), best = -1, blen = n + 1, 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 end = k;
j = m - 1;
while (j >= 0) { if (s1.charAt(k) == s2.charAt(j)) j--; k--; }
k++;
if (end - k + 1 < blen) { blen = end - k + 1; best = k; }
i = k + 1;
}
return best < 0 ? "" : s1.substring(best, best + blen);
}
}class Solution {
public:
string minWindow(string s1, string s2) {
int n = s1.size(), m = s2.size(), best = -1, blen = n + 1, 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 end = k;
j = m - 1;
while (j >= 0) { if (s1[k] == s2[j]) j--; k--; }
k++;
if (end - k + 1 < blen) { blen = end - k + 1; best = k; }
i = k + 1;
}
return best < 0 ? "" : s1.substr(best, blen);
}
};Explanation
We want the shortest chunk of s1 that still contains all of s2 in order (as a subsequence, not necessarily adjacent). The neat trick here is a two-pass scan from each starting point: go forward to find a match, then walk backward to tighten it.
Starting at index i, we move forward with two pointers and greedily match characters of s2 one by one. When we have matched the whole of s2, the index where we landed is the earliest possible end of a window that begins around i.
Now comes the clever part: from that end position we walk backward, matching s2 from its last character to its first. This pushes the left edge as far right as possible, giving the tightest window that still works. We compare its length to the best seen so far and keep the shorter one.
Example: s1 = "abcdebdde", s2 = "bde". Forward from the first b we reach the e at index 4; walking back tightens the window to "bcde", which is the shortest answer.
After processing a window we restart the forward scan just past the tightened left edge, so we never miss a shorter window. Each character is touched a bounded number of times, giving the O(n*m) running time.