Minimum window subsequence LeetCode dynamic programming solution

Question

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:

The concept is almost inspired from \$O(N log N)\$ solution for longest increasing sequence in an 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]

Answer 1

Documentation

It is good that there is a docstring for the function. You can add content to it to describe:

• A summary of its purpose, similar to the description of the challenge.
• Each input, in addition to the type already given.
• What is returned.
• The algorithm that you implemented.

Adding some comments could also help.

Naming

The PEP 8 style guide recommends snake_case for function and variable names.

minWindow would be min_window.

Perhaps you had to use certain names for submission to the LeetCode site, but S and T are not very descriptive. Perhaps string1 and string2 would be slightly better.

Also, dp and dic could use more meaningful names.

Readability

I find multiple assignments in one line like this:

global_index, starting_index, global_count = -1, -1, 1 << 31

hard to read. It is simpler to split them into multiple lines. In fact, since global_index is an unused variable, it can be deleted:

starting_index = -1
global_count = 1 << 31

I think this line should be split into 2 lines as well:

starting_index, global_count = dp[len(T)-1], i - dp[len(T)-1] + 1

This line:

return S[starting_index:starting_index + global_count]

might be clearer with parentheses:

return S[starting_index : (starting_index + global_count)]

DRY

This expression is repeated several times:

dp[len(T)-1]

It can be assigned to a variable to avoid the repetition. This may be more efficient since len is only executed once.