Distinct Subsequences II - Solution & Explanation
Problem Statement
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 <= 2000sconsists of lowercase English letters.
Approach Overview
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.
Approach 1: Dynamic Programming with Last Seen
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.
Complexity
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.
Approach 2: Space Optimized Dynamic Programming
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.
Code
Python
JavaScript
Complexity
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 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
LeetCode 940. Distinct Subsequences II (Hard) | Dynamic Programming | C++ • Ascorbichelix • 4,291 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Distinct Subsequences II easy or hard?
Distinct Subsequences II Python/Java solution
How to solve Distinct Subsequences II in O(n)?
What is the best approach for Distinct Subsequences II?
Is Distinct Subsequences II asked at Google/Amazon/Meta?
What data structure is used in Distinct Subsequences II?
What is the time complexity of Distinct Subsequences II?
Ready to solve this problem?
Practice Distinct Subsequences II with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor