Question

1987. 不同的好子序列数目

English Version

题目描述

给你一个二进制字符串 binary 。 binary 的一个 子序列 如果是 非空 的且没有 前导 0 （除非数字是 "0" 本身），那么它就是一个 好 的子序列。

请你找到 binary 不同好子序列 的数目。

• 比方说，如果 binary = "001" ，那么所有 好 子序列为 ["0", "0", "1"] ，所以 不同 的好子序列为 "0" 和 "1" 。 注意，子序列 "00" ，"01" 和 "001" 不是好的，因为它们有前导 0 。

请你返回 binary 中 不同好子序列 的数目。由于答案可能很大，请将它对 109 + 7 取余 后返回。

一个 子序列 指的是从原数组中删除若干个（可以一个也不删除）元素后，不改变剩余元素顺序得到的序列。

 

示例 1：

输入：binary = "001"
输出：2
解释：好的二进制子序列为 ["0", "0", "1"] 。
不同的好子序列为 "0" 和 "1" 。

示例 2：

输入：binary = "11"
输出：2
解释：好的二进制子序列为 ["1", "1", "11"] 。
不同的好子序列为 "1" 和 "11" 。

示例 3：

输入：binary = "101"
输出：5
解释：好的二进制子序列为 ["1", "0", "1", "10", "11", "101"] 。
不同的好子序列为 "0" ，"1" ，"10" ，"11" 和 "101" 。

 

提示：

• 1 <= binary.length <= 105
• binary 只含有 '0' 和 '1' 。

解法

方法一：动态规划

我们定义 $f$ 表示以 $1$ 结尾的不同好子序列的数目，定义 $g$ 表示以 $0$ 结尾的且以 $1$ 开头的不同好子序列的数目。初始时 $f = g = 0$。

对于一个二进制字符串，我们可以从左到右遍历每一位，假设当前位为 $c$，那么：

• 如果 $c = 0$，那么我们可以在 $f$ 和 $g$ 个不同的好子序列拼上 $c$，因此更新 $g = (g + f) \bmod (10^9 + 7)$；
• 如果 $c = 1$，那么我们可以在 $f$ 和 $g$ 个不同的好子序列拼上 $c$，同时还可以单独拼上 $c$，因此更新 $f = (f + g + 1) \bmod (10^9 + 7)$。

如果字符串包含 $0$，那么最终答案为 $f + g + 1$，否则答案为 $f + g$。

时间复杂度 $O(n)$，其中 $n$ 是字符串长度。空间复杂度 $O(1)$。

相似题目：

• 940. 不同的子序列 II

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