#1955

Count Number of Special Subsequences

candidate master · 1355 · lc hard +32 · verified · 52.7% accepted · 548 likes · top 43%

Description

A special sequence consists of one or more 0s, followed by one or more 1s, followed by one or more 2s.

Given an array nums containing only 0s, 1s, and 2s, return the number of special subsequences in nums. Two subsequences are different if they use different index sets. Return the answer modulo 10⁹ + 7.

Example 1:

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].

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 bolded:

- [0,1,2,0,1,2]

Code

1

2

3

class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:

class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int: