Valid Permutations for DI Sequence

hard dynamic programming prefix sum combinatorics

Problem

You are given a string s of length n consisting of characters 'D' and 'I'. A permutation perm of the integers 0, 1, …, n is valid when, for every index i, perm[i] > perm[i+1] if s[i] == 'D' and perm[i] < perm[i+1] if s[i] == 'I'. Return the number of valid permutations, modulo 10⁹+7.

Inputs = "DID"

Output5

The 5 valid permutations of {0,1,2,3} are 1023, 1032, 2031, 2103, 3102 (each goes Down, then Up, then Down).

s (only D and I)

def num_perms_di_sequence(s):
    MOD = 10**9 + 7
    n = len(s)
    dp = [1]                      # dp[j]: perms of first row, last rank j
    for i in range(1, n + 1):
        ndp = [0] * (i + 1)
        if s[i - 1] == 'I':
            run = 0               # prefix sum of dp[0..j-1]
            for j in range(i + 1):
                ndp[j] = run
                if j < len(dp):
                    run = (run + dp[j]) % MOD
        else:                     # 'D': suffix sum of dp[j..]
            run = 0
            for j in range(i, -1, -1):
                if j < len(dp):
                    run = (run + dp[j]) % MOD
                ndp[j] = run
        dp = ndp
    return sum(dp) % MOD

function numPermsDISequence(s) {
  const MOD = 1000000007n, n = s.length;
  let dp = [1n];
  for (let i = 1; i <= n; i++) {
    const ndp = new Array(i + 1).fill(0n);
    if (s[i - 1] === 'I') {
      let run = 0n;
      for (let j = 0; j <= i; j++) {
        ndp[j] = run;
        if (j < dp.length) run = (run + dp[j]) % MOD;
      }
    } else {
      let run = 0n;
      for (let j = i; j >= 0; j--) {
        if (j < dp.length) run = (run + dp[j]) % MOD;
        ndp[j] = run;
      }
    }
    dp = ndp;
  }
  return Number(dp.reduce((a, b) => (a + b) % MOD, 0n));
}

class Solution {
    public int numPermsDISequence(String s) {
        long MOD = 1_000_000_007L;
        int n = s.length();
        long[] dp = new long[]{1};
        for (int i = 1; i <= n; i++) {
            long[] ndp = new long[i + 1];
            if (s.charAt(i - 1) == 'I') {
                long run = 0;
                for (int j = 0; j <= i; j++) {
                    ndp[j] = run;
                    if (j < dp.length) run = (run + dp[j]) % MOD;
                }
            } else {
                long run = 0;
                for (int j = i; j >= 0; j--) {
                    if (j < dp.length) run = (run + dp[j]) % MOD;
                    ndp[j] = run;
                }
            }
            dp = ndp;
        }
        long ans = 0;
        for (long v : dp) ans = (ans + v) % MOD;
        return (int) ans;
    }
}

int numPermsDISequence(string s) {
    const long long MOD = 1000000007LL;
    int n = s.size();
    vector<long long> dp(1, 1);
    for (int i = 1; i <= n; i++) {
        vector<long long> ndp(i + 1, 0);
        if (s[i - 1] == 'I') {
            long long run = 0;
            for (int j = 0; j <= i; j++) {
                ndp[j] = run;
                if (j < (int)dp.size()) run = (run + dp[j]) % MOD;
            }
        } else {
            long long run = 0;
            for (int j = i; j >= 0; j--) {
                if (j < (int)dp.size()) run = (run + dp[j]) % MOD;
                ndp[j] = run;
            }
        }
        dp = ndp;
    }
    long long ans = 0;
    for (long long v : dp) ans = (ans + v) % MOD;
    return (int) ans;
}

Explanation

This counts permutations that go down (D) or up (I) at each step. The trick is to track not the actual numbers but the relative rank of the last placed element among the numbers used so far. dp[j] = number of valid arrangements where the last element is the j-th smallest available.

We build the table row by row, adding one more number each time. When the next character is 'I' (must go up), the new last element must be larger than the previous one, so ndp[j] sums all dp values with smaller rank — a prefix sum.

When the character is 'D' (must go down), the new element must be smaller, so ndp[j] sums all dp values with larger rank — a suffix sum. Using running sums makes each row cost O(n) instead of O(n²).

Everything is taken modulo 10⁹+7 because the counts grow huge.

Example: s = "DID" gives 5 valid permutations of {0,1,2,3} (such as 1023 and 2103), which is the sum of the final dp row.

Time: O(n²) Space: O(n)