Skip to content

1955. Count Number of Special Subsequences

SourceWeekly Contest 252 Q4DifficultyHardRating2125

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 109 + 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 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]
- [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 <= 105
  • 0 <= nums[i] <= 2

Solutions

Solution 1: Dynamic Programming

Thinking

A special subsequence is ones of \(0\)s, then \(1\)s, then \(2\)s. There are exponentially many subsequences, so we count by ending value.

\(f[i][j]\) is the number among the first \(i\) elements that end with \(j\). A \(0\) doubles previous \(0\)-sequences plus a new singleton; \(1\) and \(2\) append to the previous stage or the same stage.

The answer is \(f[n-1][2]\) modulo \(10^9+7\).

We define \(f[i][j]\) to represent the number of special subsequences ending with \(j\) among the first \(i+1\) elements. Initially, \(f[i][j]=0\), and if \(nums[0]=0\), then \(f[0][0]=1\).

For \(i \gt 0\), we consider the value of \(nums[i]\):

If \(nums[i] = 0\): If we do not choose \(nums[i]\), then \(f[i][0] = f[i-1][0]\); if we choose \(nums[i]\), then \(f[i][0]=f[i-1][0]+1\), because we can add a \(0\) to the end of any special subsequence ending with \(0\) to get a new special subsequence, or we can use \(nums[i]\) alone as a special subsequence. Therefore, \(f[i][0] = 2 \times f[i - 1][0] + 1\). The rest of \(f[i][j]\) is equal to \(f[i-1][j]\).

If \(nums[i] = 1\): If we do not choose \(nums[i]\), then \(f[i][1] = f[i-1][1]\); if we choose \(nums[i]\), then \(f[i][1]=f[i-1][1]+f[i-1][0]\), because we can add a \(1\) to the end of any special subsequence ending with \(0\) or \(1\) to get a new special subsequence. Therefore, \(f[i][1] = f[i-1][0] + 2 \times f[i - 1][1]\). The rest of \(f[i][j]\) is equal to \(f[i-1][j]\).

If \(nums[i] = 2\): If we do not choose \(nums[i]\), then \(f[i][2] = f[i-1][2]\); if we choose \(nums[i]\), then \(f[i][2]=f[i-1][2]+f[i-1][1]\), because we can add a \(2\) to the end of any special subsequence ending with \(1\) or \(2\) to get a new special subsequence. Therefore, \(f[i][2] = f[i-1][1] + 2 \times f[i - 1][2]\). The rest of \(f[i][j]\) is equal to \(f[i-1][j]\).

In summary, we can get the following state transition equations:

\[ \begin{aligned} f[i][0] &= 2 \times f[i - 1][0] + 1, \quad nums[i] = 0 \\ f[i][1] &= f[i-1][0] + 2 \times f[i - 1][1], \quad nums[i] = 1 \\ f[i][2] &= f[i-1][1] + 2 \times f[i - 1][2], \quad nums[i] = 2 \\ f[i][j] &= f[i-1][j], \quad nums[i] \neq j \end{aligned} \]

The final answer is \(f[n-1][2]\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the array \(nums\).

Similar code found with 1 license type

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        n = len(nums)
        f = [[0] * 3 for _ in range(n)]
        f[0][0] = nums[0] == 0
        for i in range(1, n):
            if nums[i] == 0:
                f[i][0] = (2 * f[i - 1][0] + 1) % mod
                f[i][1] = f[i - 1][1]
                f[i][2] = f[i - 1][2]
            elif nums[i] == 1:
                f[i][0] = f[i - 1][0]
                f[i][1] = (f[i - 1][0] + 2 * f[i - 1][1]) % mod
                f[i][2] = f[i - 1][2]
            else:
                f[i][0] = f[i - 1][0]
                f[i][1] = f[i - 1][1]
                f[i][2] = (f[i - 1][1] + 2 * f[i - 1][2]) % mod
        return f[n - 1][2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countSpecialSubsequences(int[] nums) {
        final int mod = (int) 1e9 + 7;
        int n = nums.length;
        int[][] f = new int[n][3];
        f[0][0] = nums[0] == 0 ? 1 : 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == 0) {
                f[i][0] = (2 * f[i - 1][0] % mod + 1) % mod;
                f[i][1] = f[i - 1][1];
                f[i][2] = f[i - 1][2];
            } else if (nums[i] == 1) {
                f[i][0] = f[i - 1][0];
                f[i][1] = (f[i - 1][0] + 2 * f[i - 1][1] % mod) % mod;
                f[i][2] = f[i - 1][2];
            } else {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1];
                f[i][2] = (f[i - 1][1] + 2 * f[i - 1][2] % mod) % mod;
            }
        }
        return f[n - 1][2];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        const int mod = 1e9 + 7;
        int n = nums.size();
        int f[n][3];
        memset(f, 0, sizeof(f));
        f[0][0] = nums[0] == 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == 0) {
                f[i][0] = (2 * f[i - 1][0] % mod + 1) % mod;
                f[i][1] = f[i - 1][1];
                f[i][2] = f[i - 1][2];
            } else if (nums[i] == 1) {
                f[i][0] = f[i - 1][0];
                f[i][1] = (f[i - 1][0] + 2 * f[i - 1][1] % mod) % mod;
                f[i][2] = f[i - 1][2];
            } else {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1];
                f[i][2] = (f[i - 1][1] + 2 * f[i - 1][2] % mod) % mod;
            }
        }
        return f[n - 1][2];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func countSpecialSubsequences(nums []int) int {
    const mod = 1e9 + 7
    n := len(nums)
    f := make([][3]int, n)
    if nums[0] == 0 {
        f[0][0] = 1
    }
    for i := 1; i < n; i++ {
        if nums[i] == 0 {
            f[i][0] = (2*f[i-1][0] + 1) % mod
            f[i][1] = f[i-1][1]
            f[i][2] = f[i-1][2]
        } else if nums[i] == 1 {
            f[i][0] = f[i-1][0]
            f[i][1] = (f[i-1][0] + 2*f[i-1][1]) % mod
            f[i][2] = f[i-1][2]
        } else {
            f[i][0] = f[i-1][0]
            f[i][1] = f[i-1][1]
            f[i][2] = (f[i-1][1] + 2*f[i-1][2]) % mod
        }
    }
    return f[n-1][2]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function countSpecialSubsequences(nums: number[]): number {
    const mod = 1e9 + 7;
    const n = nums.length;
    const f: number[][] = Array(n)
        .fill(0)
        .map(() => Array(3).fill(0));
    f[0][0] = nums[0] === 0 ? 1 : 0;
    for (let i = 1; i < n; ++i) {
        if (nums[i] === 0) {
            f[i][0] = (((2 * f[i - 1][0]) % mod) + 1) % mod;
            f[i][1] = f[i - 1][1];
            f[i][2] = f[i - 1][2];
        } else if (nums[i] === 1) {
            f[i][0] = f[i - 1][0];
            f[i][1] = (f[i - 1][0] + ((2 * f[i - 1][1]) % mod)) % mod;
            f[i][2] = f[i - 1][2];
        } else {
            f[i][0] = f[i - 1][0];
            f[i][1] = f[i - 1][1];
            f[i][2] = (f[i - 1][1] + ((2 * f[i - 1][2]) % mod)) % mod;
        }
    }
    return f[n - 1][2];
}

Solution 2: Dynamic Programming (Space Optimization)

Thinking

Only three previous counters are needed, so an in-place array of length \(3\) drops extra space to constant.

We notice that in the above state transition equations, the value of \(f[i][j]\) is only related to \(f[i-1][j]\). Therefore, we can remove the first dimension and optimize the space complexity to \(O(1)\).

We can use an array \(f\) of length 3 to represent the number of special subsequences ending with 0, 1, and 2, respectively. For each element in the array, we update the array \(f\) according to the value of the current element.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\). Where \(n\) is the length of the array \(nums\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        n = len(nums)
        f = [0] * 3
        f[0] = nums[0] == 0
        for i in range(1, n):
            if nums[i] == 0:
                f[0] = (2 * f[0] + 1) % mod
            elif nums[i] == 1:
                f[1] = (f[0] + 2 * f[1]) % mod
            else:
                f[2] = (f[1] + 2 * f[2]) % mod
        return f[2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countSpecialSubsequences(int[] nums) {
        final int mod = (int) 1e9 + 7;
        int n = nums.length;
        int[] f = new int[3];
        f[0] = nums[0] == 0 ? 1 : 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == 0) {
                f[0] = (2 * f[0] % mod + 1) % mod;
            } else if (nums[i] == 1) {
                f[1] = (f[0] + 2 * f[1] % mod) % mod;
            } else {
                f[2] = (f[1] + 2 * f[2] % mod) % mod;
            }
        }
        return f[2];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        const int mod = 1e9 + 7;
        int n = nums.size();
        int f[3]{0};
        f[0] = nums[0] == 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == 0) {
                f[0] = (2 * f[0] % mod + 1) % mod;
            } else if (nums[i] == 1) {
                f[1] = (f[0] + 2 * f[1] % mod) % mod;
            } else {
                f[2] = (f[1] + 2 * f[2] % mod) % mod;
            }
        }
        return f[2];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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];
}

Comments