Number of stable subsequences

Array Dynamic Programming

60.1% acceptance

Feb 25, 2026

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^9 + 7.

Solution

Rust

Time O(n * m)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_stable_subsequences(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    // dp[last_parity][run_length] = count of subsequences ending with 'run_length' consecutive
    // elements of 'last_parity'. run_length can be 1 or 2 (3 is invalid).
    // dp[p][1] = count of subseqs ending with exactly 1 consecutive element of parity p.
    // dp[p][2] = count of subseqs ending with exactly 2 consecutive elements of parity p.
    // Empty subsequence: dp[neutral] = 1, but we track empty separately.
    let mut dp = [[0i64; 3]; 2]; // dp[parity][run], run=1 or 2; index 0=empty
    let empty = 1i64;
    let mut total = 0i64;
    for &v in &nums {
      let p = (v & 1) as usize; // 0=even, 1=odd
      let q = 1 - p; // other parity
      // New dp values for current element v:
      // - Start a new subseq of length 1 ending with p: from empty subseq
      let _new_p1 = (empty + dp[q][1] + dp[q][2] + dp[p][1]) % MOD;
      //   Wait: can we extend dp[p][1]? That would give run=2, so yes.
      //   Extend dp[p][1]: run becomes 2 → dp[p][2]
      //   Extend dp[p][2]: run becomes 3 → INVALID
      //   Extend dp[q][1]: run starts fresh at 1 for p → dp[p][1]
      //   Extend dp[q][2]: same → dp[p][1]
      //   Extend empty: dp[p][1]
      // So:
      //   dp[p][1] += empty + dp[q][1] + dp[q][2]
      //   dp[p][2] += dp[p][1] (old)
      let add_p1 = (empty + dp[q][1] + dp[q][2]) % MOD;
      let add_p2 = dp[p][1];
      dp[p][2] = (dp[p][2] + add_p2) % MOD;
      dp[p][1] = (dp[p][1] + add_p1) % MOD;
      total = (total + add_p1 + add_p2) % MOD;
    }
    total as i32
  }
}