Formatted question description: https://leetcode.ca/all/1987.html

# 1987. Number of Unique Good Subsequences

## Level

Hard

## Description

You are given a binary string `binary`

. A **subsequence** of `binary`

is considered **good** if it is **not empty** and has **no leading zeros** (with the exception of `"0"`

).

Find the number of **unique good subsequences** of `binary`

.

- For example, if
`binary = "001"`

, then all the**good**subsequences are`["0", "0", "1"]`

, so the**unique**good subsequences are`"0"`

and`"1"`

. Note that subsequences`"00"`

,`"01"`

, and`"001"`

are not good because they have leading zeros.

Return *the number of unique good subsequences of binary*. Since the answer may be very large, return it

**modulo**

`10^9 + 7`

.A **subsequence** is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

**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”.

**Constraints:**

`1 <= binary.length <= 10^5`

`binary`

consists of only`'0'`

s and`'1'`

s.

## Solution

Use dynamic programming. Create an array `dp`

of length `binary.length() + 1`

, where `dp[i]`

represents the number of unique good subsequences among the first `i`

characters of `binary`

. Find the first character that is `'1'`

in `binary`

, which is at index `startIndex`

, and set `dp[startIndex + 1] = 1`

. Then calculate the values of `dp`

starting from `dp[startIndex + 2]`

to the end. If there exists character `'0'`

in `binary`

, add 1 to the answer since a single `'0'`

is also a good subsequence. Finally, return the answer.

```
class Solution {
public int numberOfUniqueGoodSubsequences(String binary) {
final int MODULO = 1000000007;
int length = binary.length();
int zeroCount = 0;
for (int i = 0; i < length; i++) {
if (binary.charAt(i) == '0') {
zeroCount = 1;
break;
}
}
int startIndex = -1;
for (int i = 0; i < length; i++) {
if (binary.charAt(i) == '1') {
startIndex = i;
break;
}
}
if (startIndex < 0)
return 1;
int[] dp = new int[length + 1];
dp[startIndex + 1] = 1;
int[] last = new int[2];
Arrays.fill(last, -1);
for (int i = startIndex + 1; i < length; i++) {
int index = binary.charAt(i) - '0';
dp[i + 1] = dp[i] * 2 % MODULO;
if (last[index] >= 0)
dp[i + 1] = (dp[i + 1] - dp[last[index]]) % MODULO;
dp[i + 1] = (dp[i + 1] + MODULO) % MODULO;
last[index] = i;
}
int distinctSubsequences = (dp[length] + zeroCount) % MODULO;
return distinctSubsequences;
}
}
```