Number of Unique Good Subsequences

1
2
3
4
5
6
7

class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        mod = 10**9 + 7
        dp = [0, 0]
        for char in binary:
            dp[int(char)] = (sum(dp) + int(char)) % mod
        return (sum(dp) + ('0' in binary)) % mod

10 Prerequisite LeetCode Problems

To tackle this, you should have a good understanding of dynamic programming (DP), binary numbers, and dealing with subsequences. Here are 10 problems to prepare:

  1. 300. Longest Increasing Subsequence: An essential problem to understand the basic idea of dealing with subsequences using dynamic programming.

  2. 673. Number of Longest Increasing Subsequence: An extension of the previous problem which also counts the number of longest increasing subsequences.

  3. 1143. Longest Common Subsequence: A classical problem in dynamic programming to understand how to compute the longest common subsequence.

  4. 1048. Longest String Chain: This problem requires a combination of string manipulation and dynamic programming.

  5. 516. Longest Palindromic Subsequence: An extension of the longest common subsequence problem, but within a single string.

  6. 931. Minimum Falling Path Sum: A problem to understand how dynamic programming can be used to find minimum paths.

  7. 646. Maximum Length of Pair Chain: This problem is about finding the longest chain of pairs, a concept that can be useful for subsequences.

  8. 918. Maximum Sum Circular Subarray: A twist on the classic maximum subarray problem where the subarray can be circular.

  9. 91. Decode Ways: This is a DP problem where you count the number of ways to decode a string.

  10. 509. Fibonacci Number: A simple DP problem to understand the basic concept of dynamic programming.

Working on these problems will give you a solid foundation in dynamic programming and subsequences, which are necessary for solving “1987. Number of Unique Good Subsequences”.