distinct-subsequences-ii

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given a string s, return the number of distinct non-empty subsequences of <code>s</code>. Since the answer may be very large, return it modulo <code>109 + 7</code>.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;abcde&quot;</code> while <code>&quot;aec&quot;</code> is not.
&nbsp;
Example 1:

<pre>
Input: s = &quot;abc&quot;
Output: 7
Explanation: The 7 distinct subsequences are &quot;a&quot;, &quot;b&quot;, &quot;c&quot;, &quot;ab&quot;, &quot;ac&quot;, &quot;bc&quot;, and &quot;abc&quot;.
</pre>

Example 2:

<pre>
Input: s = &quot;aba&quot;
Output: 6
Explanation: The 6 distinct subsequences are &quot;a&quot;, &quot;b&quot;, &quot;ab&quot;, &quot;aa&quot;, &quot;ba&quot;, and &quot;aba&quot;.
</pre>

Example 3:

<pre>
Input: s = &quot;aaa&quot;
Output: 3
Explanation: The 3 distinct subsequences are &quot;a&quot;, &quot;aa&quot; and &quot;aaa&quot;.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

distinctSubseqII

Distinct Subsequences II

Number of Unique Good Subsequences

number-of-unique-good-subsequences

不同的好子序列数目

Count K-Subsequences of a String With Maximum Beauty

count-k-subsequences-of-a-string-with-maximum-beauty

统计一个字符串的 k 子序列美丽值最大的数目

String

Dynamic Programming

给定一个字符串 <code>s</code>，计算 <code>s</code> 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 <code>10^9 + 7</code> 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

<ul>
	<li>例如，<code>"ace"</code> 是 <code>"abcde"</code> 的一个子序列，但 <code>"aec"</code> 不是。</li>
</ul>

&nbsp;

示例 1：

<pre>
输入：s = "abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
</pre>

示例 2：

<pre>
输入：s = "aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
</pre>

示例 3：

<pre>
输入：s = "aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code> 仅由小写英文字母组成</li>
</ul>

&nbsp;