What is the number of unique good subsequences in the problem "Number of Unique Good Subsequences"?

The problem asks you to count subsequences of a binary string that do not contain leading zeros, with the exception of '0', and return the count modulo 10^9 + 7.

How do I approach the "Number of Unique Good Subsequences" problem using dynamic programming?

You can use dynamic programming to track subsequences ending with '0' and '1'. Transition through each character while applying the modulo operation to avoid overflow.

What are the common pitfalls in solving "Number of Unique Good Subsequences"?

Key pitfalls include mishandling leading zeros, incorrect application of the modulo operation, and overcounting subsequences without considering uniqueness.

How does state transition dynamic programming apply to this problem?

State transition dynamic programming helps track how subsequences evolve as you move through the string, considering whether each character contributes to a new valid subsequence.

Why is the answer for "Number of Unique Good Subsequences" taken modulo 10^9 + 7?

The modulo operation ensures that the large numbers resulting from the subsequence count do not exceed computational limits, keeping the output manageable and correct.

#1987

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

不同的好子序列数目

给你一个二进制字符串 binary 。 binary 的一个子序列如果是非空的且没有前导 0 （除非数字是 "0" 本身），那么它就是一个好的子序列。请你找到 binary 不同好子序列的数目。比方说，如果 binary = "001" ，那么所有好子序列为 ["0", "0…

字符串动态规划

题目描述

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

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

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

请你返回 binary 中 不同好子序列 的数目。由于答案可能很大，请将它对 10⁹ + 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 <= 10⁵
binary 只含有 '0' 和 '1' 。

lightbulb

解题思路

方法一：动态规划

我们定义 $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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check the candidate's understanding of dynamic programming and state transitions.
question_mark
Evaluate their approach to handling large input sizes efficiently.
question_mark
Look for the ability to handle modular arithmetic correctly in solutions.

warning

常见陷阱

外企场景

error
Forgetting to account for leading zeros in subsequences except '0'.
error
Mismanaging the modulo operation, leading to overflow or incorrect results.
error
Not ensuring subsequences are unique, resulting in overcounting.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count subsequences where no subsequence can contain both '0' and '1'.
arrow_right_alt
Find the number of good subsequences where each subsequence contains at least one '1'.
arrow_right_alt
Return the sum of lengths of all unique good subsequences modulo 10^9 + 7.

help

常见问题

外企场景

继续练习

#1977 划分数字的方案数 #2002 两个回文子序列长度的最大乘积 #2019 解出数学表达式的学生分数