count-number-of-special-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

A sequence is special if it consists of a positive number of <code>0</code>s, followed by a positive number of <code>1</code>s, then a positive number of <code>2</code>s.

<ul>
	<li>For example, <code>[0,1,2]</code> and <code>[0,0,1,1,1,2]</code> are special.</li>
	<li>In contrast, <code>[2,1,0]</code>, <code>[1]</code>, and <code>[0,1,2,0]</code> are not special.</li>
</ul>

Given an array <code>nums</code> (consisting of only integers <code>0</code>, <code>1</code>, and <code>2</code>), return the number of different subsequences that are special. Since the answer may be very large, return it modulo <code>109 + 7</code>.

A subsequence of an array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. Two subsequences are different if the set of indices chosen are different.

&nbsp;
Example 1:

<pre>
Input: nums = [0,1,2,2]
Output: 3
Explanation: The special subsequences are bolded [0,1,2,2], [0,1,2,2], and [0,1,2,2].
</pre>

Example 2:

<pre>
Input: nums = [2,2,0,0]
Output: 0
Explanation: There are no special subsequences in [2,2,0,0].
</pre>

Example 3:

<pre>
Input: nums = [0,1,2,0,1,2]
Output: 7
Explanation: The special subsequences are bolded:
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2</code></li>
</ul>

countSpecialSubsequences

Count Number of Special Subsequences

Array

Dynamic Programming

特殊序列 是由&nbsp;正整数&nbsp;个 <code>0</code>&nbsp;，紧接着&nbsp;正整数&nbsp;个 <code>1</code>&nbsp;，最后 正整数&nbsp;个 <code>2</code>&nbsp;组成的序列。

<ul>
	<li>比方说，<code>[0,1,2]</code> 和&nbsp;<code>[0,0,1,1,1,2]</code>&nbsp;是特殊序列。</li>
	<li>相反，<code>[2,1,0]</code>&nbsp;，<code>[1]</code>&nbsp;和&nbsp;<code>[0,1,2,0]</code>&nbsp;就不是特殊序列。</li>
</ul>

给你一个数组&nbsp;<code>nums</code>&nbsp;（仅&nbsp;包含整数&nbsp;<code>0</code>，<code>1</code>&nbsp;和&nbsp;<code>2</code>），请你返回 不同特殊子序列的数目&nbsp;。由于答案可能很大，请你将它对&nbsp;<code>109 + 7</code> 取余 后返回。

一个数组的 子序列&nbsp;是从原数组中删除零个或者若干个元素后，剩下元素不改变顺序得到的序列。如果两个子序列的 下标集合&nbsp;不同，那么这两个子序列是 不同的&nbsp;。

&nbsp;

示例 1：

<pre>
输入：nums = [0,1,2,2]
输出：3
解释：特殊子序列为 [0,1,2,2]，[0,1,2,2] 和 [0,1,2,2] 。
</pre>

示例 2：

<pre>
输入：nums = [2,2,0,0]
输出：0
解释：数组 [2,2,0,0] 中没有特殊子序列。
</pre>

示例 3：

<pre>
输入：nums = [0,1,2,0,1,2]
输出：7
解释：特殊子序列包括：
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2</code></li>
</ul>