Distinct Subsequences II

Problem Description

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.

Key Insights

• A subsequence can be formed by choosing to include or exclude each character in the string.
• The number of distinct subsequences can be derived using dynamic programming.
• Care must be taken to avoid counting duplicate subsequences caused by repeating characters.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we will use dynamic programming to keep track of the number of distinct subsequences up to each character in the string. We will maintain an array dp where dp[i] represents the number of distinct subsequences that can be formed from the substring s[0:i].

1. Initialize a variable to keep track of the total number of distinct subsequences.
2. Use a map to remember the last seen index of each character to handle duplicates.
3. For each character in the string, calculate the number of distinct subsequences by considering both including and excluding the character.
4. Update the dp array and the last seen index of the character.
5. Return the total count of distinct subsequences modulo 10^9 + 7.

Code Solutions