Problem statement

https://leetcode.com/problems/minimum-window-subsequence/

Solution 1

For each letter it T and for any place from 0, 1, ..., n-1 find the place with the next index of this letter. Complexity of this step is O(26n). Then for each place form 0 to n - m we try to build the smallest window.

Complexity

Time complexity is O(26n), space complexity O(26n) as well.

Code

class Solution:
    def minWindow(self, S, T):
        n, m = len(S), len(T)
        def letter_get(s, letter, dr):
            res, cur = [-1]*len(s), -1
            for i in range(len(s))[::dr]:
                if s[i] == letter: cur = i
                res[i] = cur
            return res

        corrs = defaultdict(list)
        for letter in set(T):
            corrs[letter] = letter_get(S, letter, -1)

        win = (float("inf"), float("inf"))
        
        for i in range(n - m + 1):
            if S[i] != T[0] : continue
            q, good = i, True
            good = True
            for j in range(1, m):
                q = corrs[T[j]][q+1] 
                if q == -1 or (q == n-1 and j < m - 1): 
                    good = False
                    break
                
            if good: 
                win = min(win, (q - i + 1, i))

        return S[win[1]:win[1] + win[0]] if win[0] != float("inf") else ""

Solution 2

There is alternative solution: create a two-dimensional dp array with size n x m, where dp[i][j] represents the length of the minimum window corresponding to the ending at position i of S and T[:j].

Match each position in S and T:

  1. If S[i] != T[j], then dp[i][j] = dp[i-1][j] + 1.
  2. If S[i] == T[j], then dp[i][j] = max(dp[i-1][j]+1, dp[i-1][j-1]+1)

Complexity

Time and space complexity is O(mn).

Code

class Solution:
    def minWindow(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 ""