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 0s, followed by a positive number of 1s, then a positive number of 2s.

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

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];
}

All Problems

All Solutions