3686. Number of Stable Subsequences Hard

1/**
2 * [3686] Number of Stable Subsequences
3 *
4 * You are given an integer array nums.
5 * A <span data-keyword="subsequence-array-nonempty">subsequence</span> is stable if it does not contain three consecutive elements with the same parity when the subsequence is read in order (i.e., consecutive inside the subsequence).
6 * Return the number of stable subsequences.
7 * Since the answer may be too large, return it modulo 10^9 + 7.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">nums = [1,3,5]</span>
12 * Output: <span class="example-io">6</span>
13 * Explanation:
14 * 
15 * 	Stable subsequences are [1], [3], [5], [1, 3], [1, 5], and [3, 5].
16 * 	Subsequence [1, 3, 5] is not stable because it contains three consecutive odd numbers. Thus, the answer is 6.
17 * </div>
18 * <strong class="example">Example 2:
19 * <div class="example-block">
20 * Input: <span class="example-io">nums = </span>[2,3,4,2]
21 * Output: <span class="example-io">14</span>
22 * Explanation:
23 * 
24 * 	The only subsequence that is not stable is [2, 4, 2], which contains three consecutive even numbers.
25 * 	All other subsequences are stable. Thus, the answer is 14.
26 * </div>
27 *  
28 * Constraints:
29 * 
30 * 	1 <= nums.length <= 10^5
31 * 	1 <= nums[i] <= 10^​​​​​​​5
32 * 
33 */
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/number-of-stable-subsequences/
37// discuss: https://leetcode.com/problems/number-of-stable-subsequences/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41impl Solution {
42    pub fn count_stable_subsequences(nums: Vec<i32>) -> i32 {
43        0
44    }
45}
46
47// submission codes end
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test_3686() {
55    }
56}
57