原文链接: https://leetcode-cn.com/problems/number-of-unique-good-subsequences

英文原文

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.

中文题目

给你一个二进制字符串 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' 。

通过代码

高赞题解

相似题目

940.不同的子序列II

解题思路

定义

因为我们关心子序列的 开头 是什么，所以我们这样定义：

$dp[i][0]=$ 字符串 binary 的从 $i$ 开始的子串中，以 $0$ 开头的子序列的个数

$dp[i][1]=$ 字符串 binary 的从 $i$ 开始的子串中，以 $1$ 开头的子序列的个数

状态转移

我们从后向前遍历字符串 binary 。

• 当 binary[i] == ‘0’ 时，$dp[i][0]$ 的求解可以分成 $3$ 个部分：

  • 第一部分：这个 ‘0’ 可以添加到所有的子序列的前面，此部分共有 $dp[i+1][0] + dp[i+1][1]$ 个不同的子序列；

  • 第二部分：原有的 $dp[i+1][0]$ 个以 $0$ 开始的子序列，但是这部分不能增加到 $dp[i][0]$ 中，因为这些序列肯定包含在第一部分和第三部分中，不能重复添加；

  • 第三部分：单独的 $1$ 个 $0$。

  因此，$dp[i][0]=$ 第一部分 $+$ 第三部分 $=dp[i+1][0] + dp[i+1][1] + 1$。

  然后，由于 binary[i] == ‘0’，故 $dp[i][1]$ 不会发生变化，$dp[i][1] = dp[i+1][1]$。

• 当 binary[i] == ‘1’ 时，同理可推

  $dp[i][1] = dp[i+1][0] + dp[i+1][1] + 1$

  $dp[i][0] = dp[i+1][0]$

最终答案

最终答案就是，全部以 $1$ 开头的子序列的个数（也就是 $dp[0][1]$）+ 字符串 “0” （如果有）。

代码

代码实现采用了滚动数组的方式，空间复杂度为 $O(1)$，时间复杂度为 $O(n)$。

class Solution {
public:
    int numberOfUniqueGoodSubsequences(string s) {
        int n = s.size();
        int dp0 = 0, dp1 = 0, mod = 1e9 + 7, has0 = 0;
        for(int i = n-1; i >= 0; --i) {
            if(s[i] == '0') {
                has0 = 1;
                dp0 = (dp0 + dp1 + 1) % mod;
            } else {
                dp1 = (dp0 + dp1 + 1) % mod;
            }
        }
        return (dp1 + has0) % mod;
    }
};

统计信息

通过次数	提交次数	AC比率
1503	3199	47.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言