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.
public String minWindow(String S, String T) {
int m = S.length(), n = T.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0;
i <= m;
i++) {
for (int j = 0;
j <= n;
j++) {
dp[i][j] = Integer.MAX_VALUE;
}
}
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.charAt(i - 1) == T.charAt(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];
}
}
int minLen = Integer.MAX_VALUE, 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.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?
