#1987

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Unique Good Subsequences

Find the number of unique good subsequences of a binary string using dynamic programming and modular arithmetic.

Problem Statement

Given a binary string, find the number of unique subsequences that do not have leading zeros, except for the string '0'. A subsequence is a derived string that can be formed by deleting some or none of the characters in the original string without changing the order of the remaining characters.

Return the number of such unique good subsequences modulo 10^9 + 7. The input string can have up to 10^5 characters, so an efficient solution is required to handle the large input size.

Examples

Example 1

Input: binary = "001"

Output: 2

The good subsequences of binary are ["0", "0", "1"]. The unique good subsequences are "0" and "1".

Example 2

Input: binary = "11"

Output: 2

The good subsequences of binary are ["1", "1", "11"]. The unique good subsequences are "1" and "11".

Example 3

Input: binary = "101"

Output: 5

The good subsequences of binary are ["1", "0", "1", "10", "11", "101"]. The unique good subsequences are "0", "1", "10", "11", and "101".

Constraints

1 <= binary.length <= 105
binary consists of only '0's and '1's.

Solution Approach

Dynamic Programming Setup

Use dynamic programming to track the number of valid subsequences ending with '0' and '1'. Define dp arrays to store the count of good subsequences for each position in the string. Transition states based on whether the character is '0' or '1', and handle subsequences with or without the current character.

Handling Modulo Operation

Since the result can be large, apply modulo 10^9 + 7 to avoid overflow. Each step of the dynamic programming transition should include the modulo operation to ensure the result remains manageable and correct.

Final Calculation

At the end of the iteration, the dp array will contain the count of unique good subsequences. Sum the valid subsequences and return the result modulo 10^9 + 7. Ensure to account for repeated subsequences by considering only unique subsequences.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach but is typically O(n), where n is the length of the binary string, since each character in the string is processed once. Space complexity depends on the storage of the dp arrays, which is O(n) for tracking subsequences up to the current position.

What Interviewers Usually Probe

Check the candidate's understanding of dynamic programming and state transitions.
Evaluate their approach to handling large input sizes efficiently.
Look for the ability to handle modular arithmetic correctly in solutions.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for leading zeros in subsequences except '0'.
Mismanaging the modulo operation, leading to overflow or incorrect results.
Not ensuring subsequences are unique, resulting in overcounting.

Follow-up variants

Count subsequences where no subsequence can contain both '0' and '1'.
Find the number of good subsequences where each subsequence contains at least one '1'.
Return the sum of lengths of all unique good subsequences modulo 10^9 + 7.

FAQ

What is the number of unique good subsequences in the problem "Number of Unique Good Subsequences"?

The problem asks you to count subsequences of a binary string that do not contain leading zeros, with the exception of '0', and return the count modulo 10^9 + 7.

How do I approach the "Number of Unique Good Subsequences" problem using dynamic programming?

You can use dynamic programming to track subsequences ending with '0' and '1'. Transition through each character while applying the modulo operation to avoid overflow.

What are the common pitfalls in solving "Number of Unique Good Subsequences"?

Key pitfalls include mishandling leading zeros, incorrect application of the modulo operation, and overcounting subsequences without considering uniqueness.

How does state transition dynamic programming apply to this problem?

State transition dynamic programming helps track how subsequences evolve as you move through the string, considering whether each character contributes to a new valid subsequence.

Why is the answer for "Number of Unique Good Subsequences" taken modulo 10^9 + 7?

The modulo operation ensures that the large numbers resulting from the subsequence count do not exceed computational limits, keeping the output manageable and correct.

terminal

Solution

Solution 1: Dynamic Programming

We define $f$ as the number of distinct good subsequences ending with $1$, and $g$ as the number of distinct good subsequences ending with $0$ and starting with $1$. Initially, $f = g = 0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        f = g = 0
        ans = 0
        mod = 10**9 + 7
        for c in binary:
            if c == "0":
                g = (g + f) % mod
                ans = 1
            else:
                f = (f + g + 1) % mod
        ans = (ans + f + g) % mod
        return ans

Continue Practicing

#1977 number of ways to separate numbers #2002 maximum product of the length of two palindromic subsequences #2019 the score of students solving math expression