BinarySearch 0752 Distinct Subsequences

Problem statement

https://binarysearch.com/problems/Distinct-Subsequences/

Solution

Equal to Leetcode 0940. Distinct Subsequences II.

Complexity

It is true O(n) for time and space.

Code

class Solution:
    def solve(self, S):
        dp, last, M = [1], {}, 10**9 + 7
        for i, x in enumerate(S):
            dp += [(dp[-1] * 2) % M]
            if x in last:
                dp[-1] -= dp[last[x]]
            last[x] = i

        return (dp[-1] - 1) % M