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.
def minWindow(S, T):
m, n = len(S), len(T); dp = [[float('inf')] * (m + 1) for _ in range(n + 1); dp[0][0] = 0; for i in range(1, m + 1):
for j in range(n + 1):
if j == 0:
dp[i][j] = 0 elif 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]; minLen, minIdx = float('inf'), -1; for i in range(1, m + 1):
if dp[i][n] < minLen:
minLen = dp[i][n]; minIdx = i; if minIdx == -1:
return ""; return S[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?
