Is Distinct Subsequences II easy or hard?

Distinct Subsequences II is classified as a Hard problem because it requires careful dynamic programming state design and handling of duplicate subsequences. Many candidates initially overcount results until they recognize the need to subtract contributions from previous occurrences.

Distinct Subsequences II Python/Java solution

Python and Java implementations follow the same dynamic programming formula: dp[i] = 2 * dp[i-1] minus the count before the last occurrence of the current character. Both languages usually store last positions in an array or dictionary and apply modulo 1e9+7 to avoid overflow.

How to solve Distinct Subsequences II in O(n)?

Use dynamic programming where dp[i] represents the number of distinct subsequences using the first i characters. For each new character, double the previous count and subtract the contribution from its previous occurrence to remove duplicates. Tracking last positions with an array or hash map ensures the algorithm processes the string in linear time.

What is the best approach for Distinct Subsequences II?

The best approach uses dynamic programming with a last-seen index for each character. Each step doubles the number of subsequences and subtracts duplicates created by earlier occurrences of the same character. This method runs in O(n) time and handles repeated characters correctly using a hash map or fixed array.

Is Distinct Subsequences II asked at Google/Amazon/Meta?

Distinct subsequence counting problems appear frequently in interviews at companies like Google, Amazon, and Meta because they test dynamic programming reasoning and duplicate handling. Variations of this problem are commonly used to evaluate DP state design and optimization skills.

What data structure is used in Distinct Subsequences II?

The solution primarily uses dynamic programming along with an auxiliary structure to track the last occurrence of each character. This is typically implemented using a hash map or a fixed array of size 26 for lowercase letters. These structures help subtract duplicate subsequences efficiently.

What is the time complexity of Distinct Subsequences II?

The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once while updating the dynamic programming state and checking the previous occurrence of the character. Space complexity is O(n) for the DP array or O(1) with the space‑optimized version.

Description Solution Video 16:49

940. Distinct Subsequences II

Hard56.7% acceptance2 companies

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⁹ + 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. (i.e., "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 <= 2000
s consists of lowercase English letters.

Asked at 2 companies

Google Amazon

Topics

Dynamic Programming String

16:49

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

940. Distinct Subsequences II

Asked at 2 companies

Topics

Similar problems