How do you solve Distinct Subsequences II on LeetCode?

Distinct Subsequences II (LeetCode #940) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The number of distinct subsequences can grow exponentially, so efficient counting is crucial.

What is the brute force solution for Distinct Subsequences II?

The brute force approach for Distinct Subsequences II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach generates all possible subsequences of the string and then filters out the distinct ones. This is straightforward but inefficient for larger strings due to the exponential growth of subsequences. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Distinct Subsequences II?

Distinct Subsequences II uses the following concepts: String, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Hash Map.

What are the interview tips for Distinct Subsequences II?

Always clarify whether the empty subsequence should be counted in the final result. Discuss your thought process and approach before jumping into coding; this shows your understanding. Practice explaining your code and logic, as interviewers often ask for clarifications.

What are common mistakes when solving Distinct Subsequences II?

Failing to account for the empty subsequence when calculating distinct counts. Not using a HashMap or similar structure to track the last occurrence of characters, leading to incorrect results.

#940

Distinct Subsequences II

Hard

StringDynamic ProgrammingDynamic ProgrammingHash Map

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses dynamic programming to calculate the number of distinct subsequences efficiently. By leveraging previously computed results, we avoid redundant calculations and achieve a linear time complexity.

⚙️

Algorithm

3 steps

1Step 1: Initialize a DP array where dp[i] represents the number of distinct subsequences for the substring s[0:i].
2Step 2: Iterate through the string, updating dp[i] based on the previous values and the last occurrence of the character.
3Step 3: Use a HashMap to track the last occurrence of each character to ensure we only count new subsequences.

solution.py15 lines

1# Full working Python code
2def distinct_subseq_optimal(s):
3    MOD = 10**9 + 7
4    n = len(s)
5    dp = [0] * (n + 1)
6    dp[0] = 1  # Base case: empty string has 1 subsequence (the empty subsequence)
7    last = {}
8
9    for i in range(1, n + 1):
10        dp[i] = (2 * dp[i - 1]) % MOD  # Double the count of previous subsequences
11        if s[i - 1] in last:
12            dp[i] = (dp[i] - dp[last[s[i - 1]] - 1]) % MOD  # Remove duplicates
13        last[s[i - 1]] = i
14
15    return (dp[n] - 1) % MOD  # Exclude the empty subsequence

ℹ

Complexity note: The time complexity is O(n) because we process each character once. The space complexity is O(n) due to the DP array used to store results.

1The number of distinct subsequences can grow exponentially, so efficient counting is crucial.
2Using dynamic programming allows us to build on previous results, reducing redundant calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.