Package g1901_2000.s1955_count_number_of_special_subsequences

Class Solution

java.lang.Object
g1901_2000.s1955_count_number_of_special_subsequences.Solution
public class Solution extends Object
1955 - Count Number of Special Subsequences.<p>Hard</p> <p>A sequence is <strong>special</strong> if it consists of a <strong>positive</strong> number of <code>0</code>s, followed by a <strong>positive</strong> number of <code>1</code>s, then a <strong>positive</strong> number of <code>2</code>s.</p> <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> <p>Given an array <code>nums</code> (consisting of <strong>only</strong> integers <code>0</code>, <code>1</code>, and <code>2</code>), return <em>the <strong>number of different subsequences</strong> that are special</em>. Since the answer may be very large, <strong>return it modulo</strong> <code>10<sup>9</sup> + 7</code>.</p> <p>A <strong>subsequence</strong> 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 <strong>different</strong> if the <strong>set of indices</strong> chosen are different.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> nums = [0,1,2,2]</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> The special subsequences are bolded [<strong>0</strong> , <strong>1</strong> , <strong>2</strong> ,2], [<strong>0</strong> , <strong>1</strong> ,2, <strong>2</strong> ], and [<strong>0</strong> , <strong>1</strong> , <strong>2</strong> , <strong>2</strong> ].</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> nums = [2,2,0,0]</p> <p><strong>Output:</strong> 0</p> <p><strong>Explanation:</strong> There are no special subsequences in [2,2,0,0].</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> nums = [0,1,2,0,1,2]</p> <p><strong>Output:</strong> 7</p> <p><strong>Explanation:</strong> The special subsequences are bolded:</p> <ul> <li> <p>[<strong>0</strong> , <strong>1</strong> , <strong>2</strong> ,0,1,2]</p> </li> <li> <p>[<strong>0</strong> , <strong>1</strong> ,2,0,1, <strong>2</strong> ]</p> </li> <li> <p>[<strong>0</strong> , <strong>1</strong> , <strong>2</strong> ,0,1, <strong>2</strong> ]</p> </li> <li> <p>[<strong>0</strong> , <strong>1</strong> ,2,0, <strong>1</strong> , <strong>2</strong> ]</p> </li> <li> <p>[<strong>0</strong> ,1,2, <strong>0</strong> , <strong>1</strong> , <strong>2</strong> ]</p> </li> <li> <p>[<strong>0</strong> ,1,2,0, <strong>1</strong> , <strong>2</strong> ]</p> </li> <li> <p>[0,1,2, <strong>0</strong> , <strong>1</strong> , <strong>2</strong> ]</p> </li> </ul> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= nums.length <= 10<sup>5</sup></code></li> <li><code>0 <= nums[i] <= 2</code></li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • countSpecialSubsequences

      public int countSpecialSubsequences(int[] nums)