#1987

Number of Unique Good Subsequences

candidate master · 1355 · lc hard +32 · verified · 52.6% accepted · 745 likes · top 43%

Description

Given a binary string binary, a subsequence is good if it is non-empty and carries no leading zeros — the single character "0" is the only exception.

For example, with binary = "001" the good subsequences are "0" and "1" (subsequences like "00" or "01" are invalid due to leading zeros).

Return the number of distinct good subsequences of binary modulo 10⁹ + 7. A subsequence is formed by deleting zero or more characters while keeping the rest in order.

Example 1:

Input: binary = "001"

Output: 2

Explanation: The good subsequences of binary are ["0", "0", "1"].

The unique good subsequences are "0" and "1".

Example 2:

Input: binary = "11"

Output: 2

Explanation: The good subsequences of binary are ["1", "1", "11"].

The unique good subsequences are "1" and "11".

Example 3:

Input: binary = "101"

Output: 5

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

The unique good subsequences are "0", "1", "10", "11", and "101".

Code

1

2

3

class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:

class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int: