Skip to content

1987. Number of Unique Good Subsequences

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

Solutions

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\).

For a binary string, we can traverse each bit from left to right. Suppose the current bit is \(c\):

  • If \(c = 0\), we can append \(c\) to the \(f\) and \(g\) distinct good subsequences, so update \(g = (g + f) \bmod (10^9 + 7)\);
  • If \(c = 1\), we can append \(c\) to the \(f\) and \(g\) distinct good subsequences, and also append \(c\) alone, so update \(f = (f + g + 1) \bmod (10^9 + 7)\).

If the string contains \(0\), the final answer is \(f + g + 1\), otherwise the answer is \(f + g\).

The time complexity is \(O(n)\), where \(n\) is the length of the string. The space complexity is \(O(1)\).

Similar problems:

 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func numberOfUniqueGoodSubsequences(binary string) (ans int) {
    const mod int = 1e9 + 7
    f, g := 0, 0
    for _, c := range binary {
        if c == '0' {
            g = (g + f) % mod
            ans = 1
        } else {
            f = (f + g + 1) % mod
        }
    }
    ans = (ans + f + g) % mod
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function numberOfUniqueGoodSubsequences(binary: string): number {
    let [f, g] = [0, 0];
    let ans = 0;
    const mod = 1e9 + 7;
    for (const c of binary) {
        if (c === '0') {
            g = (g + f) % mod;
            ans = 1;
        } else {
            f = (f + g + 1) % mod;
        }
    }
    ans = (ans + f + g) % mod;
    return ans;
}

Comments