940 Distinct Subsequences II

link Distinct Subsequences II

Thought

The very first thought here is use DFS to find all distinct subsequences. However it will time out. So my next idea is using dynamic programming to solve it. I’ll define a DP array, where DP[i + 1] stands for how many distinct subsequences if I use 0,1,…i characters to build sub sequences, end with character i. DP[0] is special because it stands for empty condition and should always be 1.

Then, the state transfer funtion is:

DP[i] = sum(DP[i-1], DP[i-2], … DP[0])

Next, lets think about dumplicate. Assume the case “abaca”. When I see the last ‘a’, what should I put in DP[5]? I should only count DP[3],DP[4] cause DP[2] + ‘a’ is already computed in DP[3]. So I put another dictionary, with character as key, its last index so far as value. Then the state transfer function change a little bit to:

DP[i] = sum(DP[i-1], DP[i-2], … DP[last_time_same_character_appears])

And remember DP[0] stands for empty result, when we count final results, we should emit it.

Code

class Solution:
    def distinctSubseqII(self, S):
        """
        :type S: str
        :rtype: int
        """
        MOD = 10**9 + 7
        N = len(S)
        DP = [0] * (N + 1)
        DP[0] = 1
        lookup = collections.defaultdict(int)
        for index, val in enumerate(S):
            q = index
            prev = lookup[val]
            DP[index + 1] = sum(DP[prev:])  % MOD
            lookup[val] = index + 1
        return sum(DP[1:]) % MOD

Runtime

Time: O(n^2)
Space: O(n)