940.md

940. Distinct Subsequences II

Solution 1 (time O(n), space O(1))

# Dynamic programming
class Solution(object):
    def distinctSubseqII(self, s):
        """
        :type s: str
        :rtype: int
        """
        mod = 10 ** 9 + 7
        pre_cnt = [0 for _ in range(26)]
        ans = 1
        for c in s:
            new_cnt = ans
            ans = (ans + new_cnt - pre_cnt[ord(c) - ord('a')]) % mod
            pre_cnt[ord(c) - ord('a')] = new_cnt
        return ans - 1