Leetcode Problem 1987. Number of Unique Good Subsequences

1987. Number of Unique Good Subsequences

Leetcode Solutions

Dynamic Programming with Two States

  1. Initialize two variables ends0 and ends1 to keep track of the number of subsequences ending with '0' and '1', respectively.
  2. Initialize a variable has0 to keep track of whether there is at least one '0' in the binary string.
  3. Iterate through each character in the binary string.
    • If the current character is '1', update ends1 to ends0 + ends1 + 1.
    • If the current character is '0', update ends0 to ends0 + ends1 and set has0 to 1.
  4. After the iteration, the result is ends0 + ends1 + has0.
  5. Return the result modulo 10^9 + 7.
UML Thumbnail

Brute Force with Bitmasking

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...