# Number of Unique Good Subsequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-unique-good-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/number-of-unique-good-subsequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Oracle](https://scaleengineer.com/companies/oracle)
---
## Problem
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** `109 + 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 <= 105`
* `binary` consists of only `'0'`s and `'1'`s.

# Approaches
## Brute-Force with Recursion and Set
This approach generates all possible non-empty subsequences of the input string. It then iterates through each generated subsequence, checks if it meets the criteria of a 'good' subsequence, and stores the unique good ones in a hash set. The final answer is the size of the set.
**Time:** O(N * 2^N), where N is the length of the binary string. There are 2^N subsequences, and for each, we perform operations (string conversion, hashing, set insertion) that can take up to O(N) time. · **Space:** O(N * 2^N). In the worst case, we might need to store a significant fraction of the 2^N subsequences in the hash set, and each can have a length up to N.
**Pros:** Simple to understand and implement the logic.; Guaranteed to be correct for small input sizes.
**Cons:** Extremely inefficient and will not pass for the given constraints.; Exceeds time and memory limits due to exponential complexity.; Involves heavy string manipulation and recursion overhead, which is slow.
### Explanation
The core idea is to explore all possibilities. We can define a recursive function that builds subsequences character by character. For each character in the input `binary` string, we have two choices: either include it in the current subsequence or not. This generates all 2^N possible subsequences.

As we generate each subsequence, we check if it's 'good'. A subsequence is good if it's the single character `"0"` or if its first character is `'1'`. We use a `HashSet` to automatically handle uniqueness; only the unique good subsequences will be stored.

While straightforward, this method is computationally expensive. Generating 2^N subsequences is infeasible for N up to 10^5.

Here is an example of what the implementation would look like. Note that this code is for conceptual understanding and will result in a 'Time Limit Exceeded' error on submission.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    Set<String> goodSubsequences = new HashSet<>();
    String binaryStr;
    int n;

    public int numberOfUniqueGoodSubsequences(String binary) {
        this.binaryStr = binary;
        this.n = binary.length();
        // Using StringBuilder for efficient string appends
        findSubsequences(0, new StringBuilder());
        return goodSubsequences.size();
    }

    private void findSubsequences(int index, StringBuilder current) {
        if (index == n) {
            if (current.length() > 0) {
                String sub = current.toString();
                // A subsequence is good if it's "0" or doesn't start with '0'.
                if (sub.equals("0") || sub.charAt(0) != '0') {
                    goodSubsequences.add(sub);
                }
            }
            return;
        }

        // Case 1: Don't include the character at binaryStr[index]
        findSubsequences(index + 1, current);

        // Case 2: Include the character at binaryStr[index]
        current.append(binaryStr.charAt(index));
        findSubsequences(index + 1, current);
        current.deleteCharAt(current.length() - 1); // Backtrack
    }
}
```
### Algorithm
- Create a `HashSet<String>` to store unique good subsequences.
- Implement a recursive function, say `findSubsequences(index, currentString)`, to generate all subsequences.
- The base case for the recursion is when `index` reaches the end of the binary string.
- In the base case, if `currentString` is not empty, check if it's a 'good' subsequence.
- A subsequence is 'good' if it is equal to `"0"` or if it does not start with `'0'`.
- If the subsequence is good, add it to the `HashSet`.
- The recursive step involves two calls: one that includes the character at the current `index` and one that doesn't.
- Initiate the process by calling `findSubsequences(0, "")`.
- The final result is the size of the `HashSet`.

## Dynamic Programming
A highly efficient approach using dynamic programming. We iterate through the binary string once, keeping track of the number of unique good subsequences ending in '0' and '1'. This avoids generating and storing the actual subsequences, leading to a linear time and constant space solution.
**Time:** O(N), where N is the length of the binary string. We perform a single pass through the string, with constant time operations at each step. · **Space:** O(1). We only use a few variables (`endsWithZero`, `endsWithOne`, `hasZero`) to store our state, regardless of the input string's length.
**Pros:** Optimal solution with linear time complexity.; Constant space complexity, making it highly memory-efficient.; Easily handles the large constraints of the problem.
**Cons:** The dynamic programming logic can be non-intuitive to derive without careful consideration of how unique subsequences are formed.
### Explanation
This problem can be solved efficiently by breaking it down. The set of unique good subsequences consists of two disjoint sets:
1. The single subsequence `"0"` (if the input contains at least one '0').
2. The set of all unique non-empty subsequences that start with '1'.

We can calculate the size of the second set using dynamic programming. Let's maintain two counts as we iterate through the string:
- `endsWithZero`: The number of unique good subsequences seen so far that end with '0'.
- `endsWithOne`: The number of unique good subsequences seen so far that end with '1'.

When we encounter a character `c`:
- If `c == '1'`: We can form new subsequences ending in '1' by appending '1' to all existing unique good subsequences. The number of such subsequences is `endsWithZero + endsWithOne`. We can also form a new subsequence, `"1"` itself. Thus, the new count for `endsWithOne` becomes `endsWithZero + endsWithOne + 1`.
- If `c == '0'`: We can form new subsequences ending in '0' by appending '0' to all existing unique good subsequences. The number of such subsequences is `endsWithZero + endsWithOne`. We don't add 1 because a subsequence starting with `"0"` is not good (the special case `"0"` is handled separately). Thus, the new count for `endsWithZero` becomes `endsWithZero + endsWithOne`.

We also track whether we've seen a '0' in the input string with a `hasZero` flag. The final answer is `(endsWithZero + endsWithOne + (hasZero ? 1 : 0)) % MOD`.

```java
class Solution {
    public int numberOfUniqueGoodSubsequences(String binary) {
        int mod = 1_000_000_007;
        long endsWithZero = 0;
        long endsWithOne = 0;
        boolean hasZero = false;

        for (char c : binary.toCharArray()) {
            if (c == '1') {
                // New subsequences ending with '1' are formed by appending '1' to:
                // - all previous good subsequences ending with '0'
                // - all previous good subsequences ending with '1'
                // - the empty subsequence (which forms "1")
                endsWithOne = (endsWithZero + endsWithOne + 1) % mod;
            } else { // c == '0'
                // New subsequences ending with '0' are formed by appending '0' to:
                // - all previous good subsequences ending with '0'
                // - all previous good subsequences ending with '1'
                // We don't add 1 because "0" itself is not a good subsequence we count here.
                endsWithZero = (endsWithZero + endsWithOne) % mod;
                hasZero = true;
            }
        }

        long result = (endsWithZero + endsWithOne) % mod;
        if (hasZero) {
            // Add 1 for the unique good subsequence "0"
            result = (result + 1) % mod;
        }

        return (int) result;
    }
}
```
### Algorithm
- Initialize two variables, `endsWithZero = 0` and `endsWithOne = 0`, to store the counts of unique good subsequences ending with '0' and '1' respectively. These subsequences must start with '1'.
- Initialize a boolean flag `hasZero = false` to track if the input string contains a '0'.
- Define the modulus `MOD = 10^9 + 7`.
- Iterate through each character `c` of the input `binary` string.
- If `c == '1'`: The new count of subsequences ending in '1' is the sum of all previously found unique good subsequences plus 1 (for the new subsequence "1"). Update `endsWithOne = (endsWithZero + endsWithOne + 1) % MOD`.
- If `c == '0'`: The new count of subsequences ending in '0' is the sum of all previously found unique good subsequences. Update `endsWithZero = (endsWithZero + endsWithOne) % MOD`. Also, set `hasZero = true`.
- After the loop, the total number of unique good subsequences starting with '1' is `(endsWithZero + endsWithOne) % MOD`.
- The final result is this total plus 1 if `hasZero` is true (to account for the unique good subsequence "0").

# Solutions
### Java

```java
class Solution {
public
  int numberOfUniqueGoodSubsequences(String binary) {
    final int mod = (int)1 e9 + 7;
    int f = 0, g = 0;
    int ans = 0;
    for (int i = 0; i < binary.length(); ++i) {
      if (binary.charAt(i) == '0') {
        g = (g + f) % mod;
        ans = 1;
      } else {
        f = (f + g + 1) % mod;
      }
    }
    ans = (ans + f + g) % mod;
    return ans;
  }
}

```

### Python

```python
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

```

### CPP

```cpp
class Solution {
public:
  int numberOfUniqueGoodSubsequences(string binary) {
    const int mod = 1e9 + 7;
    int f = 0, g = 0;
    int ans = 0;
    for (char &c : binary) {
      if (c == '0') {
        g = (g + f) % mod;
        ans = 1;
      } else {
        f = (f + g + 1) % mod;
      }
    }
    ans = (ans + f + g) % mod;
    return ans;
  }
};

```