Leetcode Problem 940. Distinct Subsequences II

940. Distinct Subsequences II

Leetcode Solutions

Dynamic Programming Approach to Count Distinct Subsequences

  1. Initialize a dp array of length n + 1, where n is the length of the string s. Set dp[0] to 1, representing the empty subsequence.
  2. Create a dictionary last to keep track of the last index where each character was seen.
  3. Iterate over the characters of the string using index i from 1 to n.
  4. For each character s[i-1], update dp[i] to 2 * dp[i-1].
  5. If s[i-1] was seen before (let's say at index j), subtract dp[j] from dp[i] to avoid double counting.
  6. Update the last dictionary with the current index for s[i-1].
  7. Since we are interested in non-empty subsequences, subtract 1 from the final result.
  8. Return dp[n] modulo 10^9 + 7.
UML Thumbnail

Backtracking Approach to Count Distinct Subsequences

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...