2
\$\begingroup\$

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.

Solution:

Concept is almost inspired from \$O(N log N)\$ solution for longest increasing sequence in a integer array presented here. Let DP[i] represent longest increasing sequence in T which matches [0:i] subsequence of S. So,

DP[j] = i if S[j] == T[i] and j == 0

DP[j] = DP[j-1] if S[j] == T[i]

And then we are looking for DP[len(T)-1].

class Solution:
    def minWindow(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: str
        """
        dp = [-1] * (len(T)+1)
        dic = {}
        for i, t in enumerate(T):
            dic.setdefault(t, []).append(i)
        global_index, starting_index, global_count = -1, -1, 1 << 31
        for i in range(len(S)):
            if S[i] in dic:
                for j in dic[S[i]][::-1]:
                    if j == 0:
                        dp[j] = i
                    else:
                        dp[j] = dp[j-1]
                if dp[len(T)-1] != -1 and (i - dp[len(T)-1] + 1) < global_count:
                    starting_index, global_count = dp[len(T)-1], i - dp[len(T)-1] + 1
        if starting_index == -1:
            return ""
        return S[starting_index:starting_index + global_count]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.