Problem statement

https://binarysearch.com/problems/Smallest-Window-Subsequence/

Solution

Equal to Leetcode 0727 Minimum Window Subsequence.

Complexity

It is O(mn) here for time and space.

Code

class Solution:
    def solve(self, S, T):
        n, m = len(S), len(T)
        dp = [[0] * (m+1) for _ in range(n+1)]
        for j in range(1, m+1):
            dp[0][j] = float("inf")   
        
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if S[i-1] != T[j-1]:
                    dp[i][j] = dp[i-1][j] + 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + 1

        ans = min((dp[j][m], j) for j in range(1, n+1))
        return S[ans[1] - ans[0]: ans[1]] if ans[0] != float("inf") else ""