Leetcode: 727. Minimum Window Subsequence

Mistake: High constant factor in the implementation.
How can we extend the solution for \(i\) to \(i+1\)? Find the smallest index \(f(i,j)=k\) where \(s[i:k]\) has \(t[j:]\) as subsequence. The problem becomes getting the minimum between \(f(i,0)\). Time complexity is \(O(n \times m)\) and space is \(O(m)\).

class Solution:
    def minWindow(self, s1: str, s2: str) -> str:
        N = len(s1)
        M = len(s2)

        cur = [float("inf")] * (M + 1)
        cur[M] = N
        ans = None
        for i in range(N - 1, -1, -1):
            new = [float("inf")] * (M + 1)
            new[M] = i
            for j in range(M):
                if s1[i] == s2[j]:
                    new[j] = cur[j + 1]
                else:
                    new[j] = cur[j]

            j = new[0]
            if j <= N and (ans is None or (j - i) <= len(ans)):
                ans = s1[i:j]
            cur = new

        return "" if ans is None else ans


assert Solution().minWindow("abcdebdde", "bde") == "bcde"
assert Solution().minWindow("jmeqksfrsdcmsiwvaovztaqenprpvnbstl", "u") == ""