Minimum Window Subsequence - Leetcode Solution

Problem Description: Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W. If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Example 1: Input: S = "abcdebdde", T = "bde" Output: "bcde" Explanation: "bcde" is the answer because it occurs before "bdde" which has the same length.

Approach: One approach to solve this problem is to use dynamic programming, where we create a 2D DP array dp[i][j] which represents the index of the i-th character in T that matches the j-th character in S. We can then iterate through the characters in S and update the DP array accordingly. Finally, we find the minimum window that covers all characters in T.

Algorithm:

1. Create a 2D DP array dp[i][j] where dp[i][j] represents the index of the i-th character in T that matches the j-th character in S. Initialize all values to -1.
2. Set dp[0][j] to j if the first character of T matches the j-th character in S.
3. Iterate through each character in S: a. If the current character in S matches the i-th character in T, update dp[i][j] with the minimum value of dp[i-1][k] where k is less than j and dp[i-1][k] != -1.
4. Find the minimum window that covers all characters in T by iterating through dp and keeping track of the smallest window.
5. Return the minimum window.

Solution in Python:

class Solution: def minWindow(self, S: str, T: str) -> str: m, n = len(T), len(S) dp = [[-1] * n for _ in range(m)] for j in range(n): if S[j] == T[0]: dp[0][j] = j for i in range(1, m): last = -1 for j in range(n): if S[j] == T[i]: dp[i][j] = last last = max(last, dp[i-1][j]) start, end = -1, len(S) for j in range(n): if dp[m-1][j] >= 0 and j - dp[m-1][j] < end - start: start, end = dp[m-1][j], j return S[start:end+1] if start >= 0 else ""

Time Complexity: The time complexity of the above algorithm is O(mn) where m and n are the lengths of T and S respectively. The space complexity is also O(mn) as we are using a 2D DP array.

1