1987-不同的好子序列数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

给你一个二进制字符串 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[i][0] 和 f[i][1] 分别表示使用字符串 binary 的第 0, 1, \cdots, i 个字符，可以构造出的以 0/1 结尾的不同的好子序列的数目。由于「好子序列」不能包含前导 0，但本身可以为 0，那么我们可以规定「好子序列」必须以 1 开始并求出答案，如果 binary 中包含 0 就再对答案增加 1。这样做可以避免处理复杂的前导 0 规则。

在进行状态转移时，我们可以考虑第 i 个字符是 0 还是 1：

  • 如果第 i 个字符是 1，那么以 0 结尾的不同的好子序列的数目不会改变，即：

    f[i][0] = f[i - 1][0]

    难点在于如何通过已经求得结果的状态求出 f[i][1] 的值。我们可以将以 0/1 结尾的不同的好子序列的数目分成三类，使用容斥原理进行计算：

    • 用 binary 的第 0, 1, \cdots, i-1 个字符可以构造出的以 1 结尾的不同好子序列，记为 A 类。显然，A 类的方案数是 f[i-1][1]；

    • 用 binary 的第 0, 1, \cdots, i 个字符可以构造出的以 1 结尾的不同好子序列，且必须使用第 i 个字符 1，记为 B 类，由于我们必须使用第 i 个字符，那么如果倒数第二个字符选择 0，方案数为 f[i-1][0]；倒数第二个字符选择 1，方案数为 f[i-1][1]；仅有唯一的字符 1，方案数为 1。因此，B 类的方案数是 f[i-1][0] + f[i-1][1] + 1。

    如果我们简单地将 A 类和 B 类的方案数进行累加，那么我们并不会得到真正的 f[i][1] 的值，这是因为虽然 A 类和 B 类的「内部」没有重复的子序列，但它们「之间」会有重复的子序列。我们设重复的这一部分为 C，如果能计算出 C 的方案数，那么通过 |A| + |B| - |C| 就能得到 f[i][1] 的值（其中 |A| 表示 A 类的方案数）。

    如何求出 C 类的方案数呢？可以发现，对于任意一个 A 类中的子序列，它的最后一个元素一定为 1，并且属于第 0, 1, \cdots, i-1 个字符。如果我们将该元素变为第 i 个字符 1，那么就将该 A 类子序列「转换」为了 B 类子序列。因此，每一个 A 类子序列都唯一地对应着一个 B 类子序列，说明 A 是 B 的子集，那么 A 和 B 的交集 C 就是 A 本身，f[i][1] 的值就是 |B|，即：

    f[i][1] = f[i - 1][0] + f[i - 1][1] + 1

  • 如果第 i 个字符是 0，那么类似地有：

    \begin{cases}
    f[i][0] = f[i - 1][0] + f[i - 1][1] \
    f[i][1] = f[i - 1][1]
    \end{cases}

    读者可以使用上面的方法进行相同的推导，这里不再赘述。

最终的答案即为 f[n - 1][0] + f[n - 1][1]，其中 n 是字符串 binary 的长度。如果 binary 中包含 0，那么答案额外增加 1。

细节

上述状态转移方程中的 f[i][0] 和 f[i][1] 均只会从 f[i - 1][0] 和 f[i - 1][1] 转移而来，因此可以使用两个变量 even 和 odd 代替数组进行状态转移。

  • 当第 i 个字符为 1 时，even 的值不变，odd 的值变为 even} + \textit{odd} + 1；

  • 当第 i 个字符为 0 时，odd 的值不变，even 的值变为 even} + \textit{odd。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
    static constexpr int mod = 1000000007;

public:
    int numberOfUniqueGoodSubsequences(string binary) {
        int even = 0, odd = 0;
        for (char ch: binary) {
            if (ch == '0') {
                even = (even + odd) % mod;
            }
            else {
                odd = (even + odd + 1) % mod;
            }
        }

        int ans = (even + odd + (binary.find('0') != string::npos)) % mod;
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        mod = 10**9 + 7

        even = odd = 0
        for ch in binary:
            if ch == "0":
                even = (even + odd) % mod
            else:
                odd = (even + odd + 1) % mod
        
        ans = (even + odd + ("0" in binary)) % mod
        return ans

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 binary 的长度。

  • 空间复杂度：O(1)。

 Comments
On this page
1987-不同的好子序列数目