Number of Unique Good Subsequences

Problem Description

Given a binary string, count the number of unique good subsequences. A good subsequence is one that is non-empty and, if it has more than one character, does not start with '0' (the string "0" itself is valid). The answer must be computed modulo 10^9+7.

Key Insights

• A subsequence is defined by deleting zero or more characters without changing the order of the remaining characters.
• The empty subsequence is not allowed.
• Subsequences starting with '1' are always valid.
• Even if a '0' appears in later positions, the subsequence "0" (a single zero) is the only valid subsequence that can start with '0'.
• Use dynamic programming by maintaining a counter for subsequences that start with '1' and using a flag for the existence of a valid "0" subsequence.
• When reading each character, update the counters by considering all ways of appending the current character to already counted subsequences.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the binary string. Space Complexity: O(1), as only a few counters are used.

Solution

The approach uses dynamic programming:

• Maintain a counter dp1 for the number of distinct good subsequences that start with '1'.
• Use a flag (or counter) existsZero that indicates whether there is at least one valid subsequence "0" (this is set if any '0' appears in the string).
• Iterate through the binary string:
  • If the current character is '1':
    Update dp1 = dp1 * 2 + 1.
    Doubling dp1 accounts for choosing or not choosing each prior subsequence and then appending '1'. The +1 accounts for the single-character subsequence "1".
  • If the current character is '0':
    Update dp1 = dp1 * 2.
    Also set existsZero = 1 (since we can have the good subsequence "0").
• The final answer is (dp1 + existsZero) modulo 10^9+7.

This approach correctly counts all unique good subsequences while avoiding duplicates and handling the special case of the subsequence "0".

Code Solutions