Minimum Window Subsequence
Given two sequences S and T, find the minimumQuestion and saidQuestion all elements of T in the same order. If no such substring exists, return an empty string.
Constraints:
- 1 <= S.length, T.length <= 10^5
- S and T consist of lowercase English letters
Examples:
Input: S = "abcdebdde", T = "bde"
Output: bcde
Explanation: The minimum window subsequence is "bcde" because it contains all elements of T in the same order.
Solutions
Dynamic Programming
Time: O(|S| * |T|)Space: O(|S| * |T|)
The solution uses dynamic programming to build a 2D table where dp[i][j] represents the minimum length of the substring ending at index i that contains the first j characters of T. The final result is the minimum length substring that contains all characters of T.
function minWindow(S, T) {
let m = S.length, n = T.length;
let dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(Infinity));
dp[0][0] = 0;
for (let i = 1;
i <= m;
i++) {
for (let j = 0;
j <= n;
j++) {
if (j === 0) {
dp[i][j] = 0;
}
else if (S[i - 1] === T[j - 1]) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1] + 1);
}
else {
dp[i][j] = dp[i - 1][j];
}
}
let minLen = Infinity, minIdx = -1;
for (let i = 1;
i <= m;
i++) {
if (dp[i][n] < minLen) {
minLen = dp[i][n];
minIdx = i;
}
}
if (minIdx === -1) {
return "";
}
return S.substring(minIdx - minLen, minIdx);
}Follow-up:
What if the sequences S and T are very large and we need to find the minimum window subsequence in real-time?
