Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1955.html
1955. Count Number of Special Subsequences
Level
Hard
Description
A sequence is special if it consists of a positive number of 0
s, followed by a positive number of 1
s, then a positive number of 2
s.
 For example,
[0,1,2]
and[0,0,1,1,1,2]
are special.  In contrast,
[2,1,0]
,[1]
, and[0,1,2,0]
are not special.
Given an array nums
(consisting of only integers 0
, 1
, and 2
), return the number of different subsequences that are special. Since the answer may be very large, return it modulo 10^9 + 7
.
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.
Example 1:
Input: nums = [0,1,2,2]
**Output: **3
Explanation: The special subsequences are [0,1,2,2], [0,1,2,2], and [0,1,2,2].
Example 2:
Input: nums = [2,2,0,0]
Output: 0
Explanation: There are no special subsequences in [2,2,0,0].
Example 3:
Input: nums = [0,1,2,0,1,2]
Output: 7
Explanation: The special subsequences are:
 [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]
Constraints:
1 <= nums.length <= 10^5
0 <= nums[i] <= 2
Solution
Use dynamic programming. Use dp[i][j]
to represent the number of special subsequences up to index i
that end with number j
. Note that the special subsequences do not necessary end with 2, but satisfy that all 0s come before 1s and all 1s come before 2s.
When i = 0
, dp[0][0] = 1
if and only if nums[0] = 0
. For i
from 1 to nums.length  1
, dp[i][0]
is calculated as dp[i  1][0] * 2 + 1
if nums[i] = 0
, and dp[i  1][0]
otherwise. For dp[i][j]
where j
is 1 or 2, if nums[i] = j
, then dp[i][j] = dp[i  1][j] * 2 + dp[i  1][j  1]
, otherwise dp[i][j] = dp[i  1][j]
. Finally, return dp[nums.length  1][2]
.

class Solution { public int countSpecialSubsequences(int[] nums) { final int MODULO = 1000000007; int length = nums.length; int[][] dp = new int[length][3]; if (nums[0] == 0) dp[0][0] = 1; for (int i = 1; i < length; i++) { int num = nums[i]; if (num == 0) dp[i][0] = (dp[i  1][0] * 2 + 1) % MODULO; else dp[i][0] = dp[i  1][0]; if (num == 1) { dp[i][1] = dp[i  1][1] * 2 % MODULO; dp[i][1] = (dp[i][1] + dp[i  1][0]) % MODULO; } else dp[i][1] = dp[i  1][1]; if (num == 2) { dp[i][2] = dp[i  1][2] * 2 % MODULO; dp[i][2] = (dp[i][2] + dp[i  1][1]) % MODULO; } else dp[i][2] = dp[i  1][2]; } return dp[length  1][2]; } }

// OJ: https://leetcode.com/problems/countnumberofspecialsubsequences/ // Time: O(N) // Space: O(1) class Solution { public: int countSpecialSubsequences(vector<int>& A) { long mod = 1e9 + 7, dp[4] = {1}; for (int n : A) { dp[n + 1] = ((dp[n + 1] * 2) % mod + dp[n]) % mod; } return dp[3]; } };

# 1955. Count Number of Special Subsequences # https://leetcode.com/problems/countnumberofspecialsubsequences class Solution: def countSpecialSubsequences(self, nums: List[int]) > int: a = b = c = 0 M = 10 ** 9 + 7 for x in nums: if x == 0: a += a + 1 elif x == 1: b += b + a else: c += c + b c %= M return c

func countSpecialSubsequences(nums []int) int { const mod = 1e9 + 7 n := len(nums) f := [3]int{} if nums[0] == 0 { f[0] = 1 } for i := 1; i < n; i++ { if nums[i] == 0 { f[0] = (2*f[0] + 1) % mod } else if nums[i] == 1 { f[1] = (f[0] + 2*f[1]) % mod } else { f[2] = (f[1] + 2*f[2]) % mod } } return f[2] }

function countSpecialSubsequences(nums: number[]): number { const mod = 1e9 + 7; const n = nums.length; const f: number[] = [0, 0, 0]; f[0] = nums[0] === 0 ? 1 : 0; for (let i = 1; i < n; ++i) { if (nums[i] === 0) { f[0] = (((2 * f[0]) % mod) + 1) % mod; f[1] = f[1]; f[2] = f[2]; } else if (nums[i] === 1) { f[0] = f[0]; f[1] = (f[0] + ((2 * f[1]) % mod)) % mod; f[2] = f[2]; } else { f[0] = f[0]; f[1] = f[1]; f[2] = (f[1] + ((2 * f[2]) % mod)) % mod; } } return f[2]; }