#940

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Distinct Subsequences II

Find the number of distinct non-empty subsequences of a string using dynamic programming and state transitions.

Problem Statement

Given a string s, return the number of distinct non-empty subsequences of s. A subsequence is a sequence that can be derived by deleting some or no characters without changing the order of the remaining characters. Since the answer may be very large, return it modulo 10^9 + 7.

For example, for the string abc, the subsequences include: "a", "b", "c", "ab", "ac", "bc", and "abc". The problem can be solved using dynamic programming by managing the state transitions that track subsequences. The approach ensures that all subsequences are counted efficiently.

Examples

Example 1

Input: s = "abc"

Output: 7

The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".

Example 2

Input: s = "aba"

Output: 6

The 6 distinct subsequences are "a", "b", "ab", "aa", "ba", and "aba".

Example 3

Input: s = "aaa"

Output: 3

The 3 distinct subsequences are "a", "aa" and "aaa".

Constraints

1 <= s.length <= 2000
s consists of lowercase English letters.

Solution Approach

Dynamic Programming State Transitions

This problem uses dynamic programming to track the number of distinct subsequences at each step. The main idea is to keep track of previously computed subsequences and their counts, adjusting the results based on the current character and previous subsequences. This approach reduces redundant computations.

Handling Large Results with Modulo Operation

Since the number of distinct subsequences can be very large, the answer is returned modulo 10^9 + 7 to avoid overflow. This ensures the solution remains efficient and feasible even with larger strings.

Optimized Space Complexity

The space complexity is reduced to O(N) by only keeping track of the current and previous states of subsequences, eliminating the need for a 2D table. This optimization allows the solution to handle large strings more efficiently.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

The time complexity is O(N) since the solution iterates through the string once, updating the state at each step. The space complexity is O(N) due to the space used for storing intermediate results for each character in the string.

What Interviewers Usually Probe

Candidate demonstrates understanding of dynamic programming with state transitions.
Candidate efficiently handles modulo operation and optimizes for large outputs.
Candidate is able to reduce space complexity while maintaining the correctness of the solution.

Common Pitfalls or Variants

Common pitfalls

Mismanaging state transitions or failing to correctly account for previously seen characters.
Overcomplicating the problem by using unnecessary extra space for subsequences.
Failing to apply the modulo operation correctly and causing overflow.

Follow-up variants

Consider an extension where the string contains multiple distinct characters and the subsequences are constrained by specific conditions.
A variant where the input string is limited to a smaller set of characters, altering the number of possible subsequences.
Another variant could involve counting subsequences that follow specific patterns or orderings within the string.

FAQ

How do I approach the Distinct Subsequences II problem?

Start by recognizing that this problem requires dynamic programming and state transitions to track subsequences. Handle large outputs with modulo operations.

What is the time complexity of the solution?

The time complexity is O(N), where N is the length of the string.

How do I optimize space for this problem?

You can optimize space by storing only the current and previous states of subsequences, reducing the space complexity to O(N).

What is the significance of modulo 10^9 + 7 in this problem?

The modulo operation ensures that the number of subsequences doesn't overflow the standard integer range, keeping the result manageable.

How does the state transition work in this problem?

At each character, the number of subsequences is updated based on the previous state, adjusting for any duplicates caused by repeating characters.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        dp = [[0] * 26 for _ in range(n + 1)]
        for i, c in enumerate(s, 1):
            k = ord(c) - ord('a')
            for j in range(26):
                if j == k:
                    dp[i][j] = sum(dp[i - 1]) % mod + 1
                else:
                    dp[i][j] = dp[i - 1][j]
        return sum(dp[-1]) % mod

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        dp = [[0] * 26 for _ in range(n + 1)]
        for i, c in enumerate(s, 1):
            k = ord(c) - ord('a')
            for j in range(26):
                if j == k:
                    dp[i][j] = sum(dp[i - 1]) % mod + 1
                else:
                    dp[i][j] = dp[i - 1][j]
        return sum(dp[-1]) % mod

Solution 3

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        dp = [[0] * 26 for _ in range(n + 1)]
        for i, c in enumerate(s, 1):
            k = ord(c) - ord('a')
            for j in range(26):
                if j == k:
                    dp[i][j] = sum(dp[i - 1]) % mod + 1
                else:
                    dp[i][j] = dp[i - 1][j]
        return sum(dp[-1]) % mod

Continue Practicing

#943 find the shortest superstring #926 flip string to monotone increasing #960 delete columns to make sorted iii