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

Examples

Example 1

1
2
3
4
5
6
7
8


    
    
    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

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6
7
8


    
    
    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

Method 1 – Dynamic Programming (Last Seen)

Intuition

We want to count all unique good subsequences (no leading zeros except for “0”). For each character, we can keep track of the number of unique good subsequences ending with ‘0’ and ‘1’. If we see a ‘1’, it can start a new good subsequence or extend any previous good subsequence. If we see a ‘0’, it can only extend previous good subsequences ending with ‘1’, but a single ‘0’ is also allowed. We use DP to avoid duplicates.

Approach

  1. Initialize two counters: end0 (ending with ‘0’), end1 (ending with ‘1’).
  2. For each character in the string:
    • If ‘1’, it can start a new subsequence or extend all previous good subsequences.
    • If ‘0’, it can extend all previous good subsequences ending with ‘1’.
  3. At the end, if there is any ‘0’ in the string, add 1 for the single ‘0’ subsequence.
  4. Return the total modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int numberOfUniqueGoodSubsequences(string binary) {
        const int MOD = 1e9+7;
        int end0 = 0, end1 = 0;
        bool has0 = false;
        for (char c : binary) {
            if (c == '1') {
                end1 = ((long long)end0 + end1 + 1) % MOD;
            } else {
                end0 = ((long long)end0 + end1) % MOD;
                has0 = true;
            }
        }
        return (end1 + (has0 ? 1 : 0)) % MOD;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func numberOfUniqueGoodSubsequences(binary string) int {
    mod := int(1e9+7)
    end0, end1 := 0, 0
    has0 := false
    for _, c := range binary {
        if c == '1' {
            end1 = (end0 + end1 + 1) % mod
        } else {
            end0 = (end0 + end1) % mod
            has0 = true
        }
    }
    if has0 {
        return (end1 + 1) % mod
    }
    return end1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int numberOfUniqueGoodSubsequences(String binary) {
        int MOD = 1_000_000_007;
        int end0 = 0, end1 = 0;
        boolean has0 = false;
        for (char c : binary.toCharArray()) {
            if (c == '1') {
                end1 = (int)(((long)end0 + end1 + 1) % MOD);
            } else {
                end0 = (end0 + end1) % MOD;
                has0 = true;
            }
        }
        return (end1 + (has0 ? 1 : 0)) % MOD;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun numberOfUniqueGoodSubsequences(binary: String): Int {
        val MOD = 1_000_000_007
        var end0 = 0
        var end1 = 0
        var has0 = false
        for (c in binary) {
            if (c == '1') {
                end1 = ((end0.toLong() + end1 + 1) % MOD).toInt()
            } else {
                end0 = ((end0.toLong() + end1) % MOD).toInt()
                has0 = true
            }
        }
        return (end1 + if (has0) 1 else 0) % MOD
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        MOD = 10**9 + 7
        end0, end1 = 0, 0
        has0 = False
        for c in binary:
            if c == '1':
                end1 = (end0 + end1 + 1) % MOD
            else:
                end0 = (end0 + end1) % MOD
                has0 = True
        return (end1 + (1 if has0 else 0)) % MOD
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn number_of_unique_good_subsequences(binary: String) -> i32 {
        let mut end0 = 0i64;
        let mut end1 = 0i64;
        let mut has0 = false;
        let m = 1_000_000_007i64;
        for c in binary.chars() {
            if c == '1' {
                end1 = (end0 + end1 + 1) % m;
            } else {
                end0 = (end0 + end1) % m;
                has0 = true;
            }
        }
        ((end1 + if has0 { 1 } else { 0 }) % m) as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    numberOfUniqueGoodSubsequences(binary: string): number {
        const MOD = 1e9+7
        let end0 = 0, end1 = 0
        let has0 = false
        for (const c of binary) {
            if (c === '1') {
                end1 = (end0 + end1 + 1) % MOD
            } else {
                end0 = (end0 + end1) % MOD
                has0 = true
            }
        }
        return (end1 + (has0 ? 1 : 0)) % MOD
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)