Number of unique good subsequences

String Dynamic Programming

52.6% acceptance

Feb 25, 2026

744

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_unique_good_subsequences(binary: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    // ends_with_0: number of unique good subsequences ending with '0' (excluding standalone "0")
    // ends_with_1: number of unique good subsequences ending with '1'
    let mut ends0: i64 = 0;
    let mut ends1: i64 = 0;
    let has_zero = binary.contains('0');
    
    for ch in binary.bytes() {
      if ch == b'0' {
        // Append '0' to all existing good subsequences
        ends0 = (ends0 + ends1) % MOD;
      } else {
        // Append '1' to all existing good subsequences, plus "1" itself
        ends1 = (ends0 + ends1 + 1) % MOD;
      }
    }
    
    let mut result = (ends0 + ends1) % MOD;
    if has_zero {
      result = (result + 1) % MOD; // add standalone "0"
    }
    result as i32
  }
}