Solution Explanation: Dynamic Programming Approach

This problem can be efficiently solved using dynamic programming. The core idea is to track the count of unique good subsequences ending in '1' and '0' separately. We maintain two variables:

• f: Represents the count of unique good subsequences ending with '1'.
• g: Represents the count of unique good subsequences ending with '0' and having at least one '1' before the trailing '0'. This condition ensures we avoid counting subsequences with leading zeros (except for "0" itself).

We iterate through the input string binary. For each character:

• If the character is '0': We can extend all existing subsequences ending in '1' (f) by appending '0'. Additionally, if we encounter a '0' the only possible good subsequence will be '0' hence setting ans =1. We also update g accordingly.
• If the character is '1': We can extend all subsequences ending in '1' (f), all subsequences ending in '0' (g), and we can also have a new subsequence consisting of only '1'. Therefore, we update f.

Finally, the total number of unique good subsequences is the sum of f, g, and a potential additional 1 (to account for the subsequence "0" if a '0' exists in the string).

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the binary string. We iterate through the string once.
• Space Complexity: O(1). We use only a constant number of variables to store the counts.

Code Implementation (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 # handle the case where only '0' is present
            else:
                f = (f + g + 1) % mod
        ans = (ans + f + g) % mod # add f and g and handle the case when '0' is present
        return ans
 

Code Implementation (Java)

class Solution {
    public int numberOfUniqueGoodSubsequences(String binary) {
        final int mod = (int) 1e9 + 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;
    }
}

The implementations in other languages (C++, Go, TypeScript) follow a very similar structure, adapting the syntax to their respective languages while maintaining the same algorithmic logic. The key is the use of f and g to track the counts and the modulo operation to handle potential integer overflow.