September 7Hard

Distinct subsequences ii

String
Dynamic Programming

Problem

Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo 10^9 + 7.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Solution

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        @cache
        def solve(i):
            if i == len(s):
                return 0, {}
            nb, starts_with = solve(i+1)
            res = 2*nb + 1 - starts_with.get(s[i], 0)
            starts_with[s[i]] = nb + 1
            return res, starts_with

        res = solve(0)[0]
        return res % (10**9 + 7)