Valid permutations for di sequence

String Dynamic Programming Prefix Sum

56.3% acceptance

Feb 25, 2026

751

You are given a string s of length n where s[i] is either: 'D' means decreasing, or 'I' means increasing. A permutation perm of n + 1 integers of all the integers in the range [0, n] is called a valid permutation if for all valid i: If s[i] == 'D', then perm[i] > perm[i + 1], and If s[i] == 'I', then perm[i] < perm[i + 1]. Return the number of valid permutations perm. Since the answer may be large, return it modulo 109 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_perms_di_sequence(s: String) -> i32 {
    let md = 1_000_000_007i64;
    let n = s.len();
    // dp[j] = # ways to place first i+1 elements s.t. last placed has relative rank j
    // relative rank j out of (i+1) means j-th smallest in {0..i}
    let s: Vec<char> = s.chars().collect();
    let mut dp = vec![1i64; 1]; // dp[0]=1 for empty prefix
    for i in 0..n {
      let mut new_dp = vec![0i64; i + 2];
      if s[i] == 'I' {
        // new_dp[j] = sum(dp[0..j]) for j in 0..=i+1
        let mut psum = 0i64;
        for j in 0..=i+1 {
          if j > 0 { psum = (psum + dp[j-1]) % md; }
          new_dp[j] = psum;
        }
      } else {
        // new_dp[j] = sum(dp[j..=i]) for j in 0..=i+1
        let mut ssum = 0i64;
        for j in (0..=i+1).rev() {
          if j <= i { ssum = (ssum + dp[j]) % md; }
          new_dp[j] = ssum;
        }
      }
      dp = new_dp;
    }
    dp.iter().fold(0, |a, &x| (a + x) % md) as i32
  }
}