Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo 109 + 7.
"ace" is a subsequence of "abcde" while "aec" is not.
Example 1:
Input: s = "abc" Output: 7 Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".
Example 2:
Input: s = "aba" Output: 6 Explanation: The 6 distinct subsequences are "a", "b", "ab", "aa", "ba", and "aba".
Example 3:
Input: s = "aaa" Output: 3 Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".
Constraints:
1 <= s.length <= 2000s consists of lowercase English letters.This approach applies dynamic programming by maintaining an array dp where dp[i] represents the number of distinct subsequences for the substring ending at the i-th character. Another structure is used to track when each character was last seen to handle duplicate contributions.
The solution uses an array dp where dp[i] represents the number of distinct subsequences using characters up to index i. We double the count of previous subsequences for each new character, as each existing subsequence can either include the new character or not. If the character has been seen before, we adjust the count to ensure subsequences are distinct by removing the contribution from its last occurrence before the current position.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string as we process each character once.
Space Complexity: O(n + 26), for storing the dp array and the last seen index of each character.
This approach optimizes the space used by reducing the need for a full array for dynamic programming calculations, utilizing only necessary data to minimize space consumption.
This Python solution does not use a dp array but instead keeps track of subsequences using only two variables, processing each character efficiently and reducing the space complexity significantly.
JavaScript
Time Complexity: O(n), for processing each character in the string.
Space Complexity: O(26), reduced by maintaining states for each character explicitly without a full dp array.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Last Seen | Time Complexity: O(n), where n is the length of the string as we process each character once. Space Complexity: O(n + 26), for storing the dp array and the last seen index of each character. |
| Space Optimized Dynamic Programming | Time Complexity: O(n), for processing each character in the string. Space Complexity: O(26), reduced by maintaining states for each character explicitly without a full dp array. |
DP 32. Distinct Subsequences | 1D Array Optimisation Technique 🔥 • take U forward • 215,314 views views
Watch 9 more video solutions →Practice Distinct Subsequences II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor