Question

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

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

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;
  }
}

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;
  }
};

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
}

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;
}