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.
string minWindow(string S, string T) {
int m = S.size(), n = T.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[0][0] = 0;
for (int i = 1;
i <= m;
i++) {
for (int j = 0;
j <= n;
j++) {
if (j == 0) {
dp[i][j] = 0;
}
else if (S[i - 1] == T[j - 1]) {
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] + 1);
}
else {
dp[i][j] = dp[i - 1][j];
}
}
int minLen = INT_MAX, minIdx = -1;
for (int i = 1;
i <= m;
i++) {
if (dp[i][n] < minLen) {
minLen = dp[i][n];
minIdx = i;
}
}
if (minIdx == -1) {
return "";
}
return S.substr(minIdx - minLen, minLen);
}Follow-up:
What if the sequences S and T are very large and we need to find the minimum window subsequence in real-time?
