4027. Number Of Stable Subsequences¶

4027. Number of Stable Subsequences

Hard

You are given an integer array nums.

A subsequence 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).

Return the number of stable subsequences.

Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [1,3,5]

Output: 6

Explanation:

Stable subsequences are [1], [3], [5], [1, 3], [1, 5], and [3, 5].
Subsequence [1, 3, 5] is not stable because it contains three consecutive odd numbers. Thus, the answer is 6.

Example 2:

Input: nums = [2,3,4,2]

Output: 14

Explanation:

The only subsequence that is not stable is [2, 4, 2], which contains three consecutive even numbers.
All other subsequences are stable. Thus, the answer is 14.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Solution¶

class Solution {
    private int dp[][][];
    private int mod = (int)(1e9 + 7);
    public int countStableSubsequences(int[] nums) {
        int n = nums.length;
        dp = new int[n + 1][4][4];
        for (int current[][] : dp)
            for (int current1[] : current)
                Arrays.fill(current1, -1);
        int res = solve(0, -1, 0, nums);
        return res;
    }

    private int solve(int ind, int prevParity, int consParity, int arr[]) {
        if (ind >= arr.length) {
            return (prevParity != -1) ? 1 : 0;
        }
        if (dp[ind][prevParity + 2][consParity] != -1)
            return dp[ind][prevParity + 2][consParity];
        long ans = 0L;
        ans += solve(ind + 1, prevParity, consParity, arr);
        int curP = arr[ind] % 2;
        if (prevParity == -1) {
            ans += solve(ind + 1, curP, 1, arr);
        } else {
            if (curP == prevParity) {
                if (consParity + 1 < 3) {
                    ans += solve(ind + 1, curP, consParity + 1, arr);
                }
            } else {
                ans += solve(ind + 1, curP, 1, arr);
            }
        }
        ans %= mod;
        dp[ind][prevParity + 2][consParity] = (int) ans;
        return dp[ind][prevParity + 2][consParity];
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]