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.Problem Overview: Given a string s, count the number of distinct non‑empty subsequences. Subsequences can be formed by deleting characters without changing the order. Duplicate subsequences caused by repeated characters must only be counted once, and the result is returned modulo 1e9 + 7.
Approach 1: Dynamic Programming with Last Seen (O(n) time, O(n) space)
This solution uses dynamic programming where dp[i] represents the number of distinct subsequences considering the first i characters. Each new character doubles the number of subsequences because every existing subsequence can either include or exclude it. However, if the character appeared before, some subsequences would be counted twice. Track the previous index of each character using a lastSeen array or map and subtract the count that existed before its previous occurrence.
The transition becomes dp[i] = 2 * dp[i-1] - dp[last[c]-1]. This subtraction removes duplicate subsequences created by the earlier occurrence of the same character. A hash map or fixed array tracks the last position of each character. Time complexity is O(n) because each character is processed once, and space complexity is O(n) for the DP table.
Approach 2: Space Optimized Dynamic Programming (O(n) time, O(1) space)
The DP array can be eliminated by storing only the contribution of subsequences that end with each character. Maintain an array end[26] where end[c] stores how many distinct subsequences currently end with character c. For each character in the string, compute the total number of subsequences so far, then update the value for that character while removing the previous contribution for duplicates.
This approach effectively tracks how many subsequences each character contributes to the final count, preventing double counting when the same letter appears again. Because the alphabet size is fixed, the memory usage becomes constant. Time complexity remains O(n) and space complexity drops to O(1).
Recommended for interviews: Interviewers usually expect the dynamic programming with last‑seen correction. It shows you understand how duplicate subsequences arise and how DP states evolve. The space‑optimized version demonstrates deeper insight by reducing memory while keeping the same O(n) time complexity.
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.
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.
Python
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. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Last Seen | O(n) | O(n) | General solution that clearly shows how duplicates are removed using last occurrence tracking |
| Space Optimized Dynamic Programming | O(n) | O(1) | When memory matters or when the alphabet size is small and fixed |
LeetCode 940. Distinct Subsequences II (Hard) | Dynamic Programming | C++ • Ascorbicindio • 4,030 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