LC-0940 Hard LeetCode

940. Distinct Subsequences II

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 43% Topics: String, Dynamic Programming

Reading material

Strings 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

import collections


class Solution(object):
    def distinctSubseqII(self, S):
        """
        :type S: str
        :rtype: int
        """
        MOD = 10**9+7
        result, dp = 0, [0]*26
        for c in S:
            result, dp[ord(c)-ord('a')] = (result+((result+1)-dp[ord(c)-ord('a')]))%MOD, (result+1)%MOD
        return result

Solution from kamyu104/LeetCode-Solutions · MIT