number-of-unique-good-subsequences

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a binary string <code>binary</code>. A subsequence of <code>binary</code> is considered good if it is not empty and has no leading zeros (with the exception of <code>&quot;0&quot;</code>).

Find the number of unique good subsequences of <code>binary</code>.

<ul>
	<li>For example, if <code>binary = &quot;001&quot;</code>, then all the good subsequences are <code>[&quot;0&quot;, &quot;0&quot;, &quot;1&quot;]</code>, so the unique good subsequences are <code>&quot;0&quot;</code> and <code>&quot;1&quot;</code>. Note that subsequences <code>&quot;00&quot;</code>, <code>&quot;01&quot;</code>, and <code>&quot;001&quot;</code> are not good because they have leading zeros.</li>
</ul>

Return the number of unique good subsequences of <code>binary</code>. Since the answer may be very large, return it modulo <code>109 + 7</code>.

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.

&nbsp;
Example 1:

<pre>
Input: binary = &quot;001&quot;
Output: 2
Explanation: The good subsequences of binary are [&quot;0&quot;, &quot;0&quot;, &quot;1&quot;].
The unique good subsequences are &quot;0&quot; and &quot;1&quot;.
</pre>

Example 2:

<pre>
Input: binary = &quot;11&quot;
Output: 2
Explanation: The good subsequences of binary are [&quot;1&quot;, &quot;1&quot;, &quot;11&quot;].
The unique good subsequences are &quot;1&quot; and &quot;11&quot;.</pre>

Example 3:

<pre>
Input: binary = &quot;101&quot;
Output: 5
Explanation: The good subsequences of binary are [&quot;1&quot;, &quot;0&quot;, &quot;1&quot;, &quot;10&quot;, &quot;11&quot;, &quot;101&quot;]. 
The unique good subsequences are &quot;0&quot;, &quot;1&quot;, &quot;10&quot;, &quot;11&quot;, and &quot;101&quot;.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= binary.length &lt;= 105</code></li>
	<li><code>binary</code> consists of only <code>&#39;0&#39;</code>s and <code>&#39;1&#39;</code>s.</li>
</ul>

numberOfUniqueGoodSubsequences

Number of Unique Good Subsequences

Distinct Subsequences

distinct-subsequences

不同的子序列

Distinct Subsequences II

distinct-subsequences-ii

不同的子序列 II

String

Dynamic Programming

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

请你找到&nbsp;<code>binary</code>&nbsp;不同好子序列&nbsp;的数目。

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

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

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

&nbsp;

示例 1：

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

示例 2：

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

示例 3：

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

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= binary.length &lt;= 105</code></li>
	<li><code>binary</code>&nbsp;只含有&nbsp;<code>'0'</code>&nbsp;和&nbsp;<code>'1'</code> 。</li>
</ul>