Distinct Subsequences II - Video Solutions
LeetCode 940. Distinct Subsequences II (Hard) | Dynamic Programming | C++
Distinct Subsequences II - Video Solution
Watch 10 video solutions for Distinct Subsequences II, a hard level problem involving String, Dynamic Programming. This walkthrough by Ascorbichelix has 4,291 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |