903. Valid Permutations for DI Sequence

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

Example 1:

Input: s = “DID”
Output: 5
Explanation: The 5 valid permutations of (0, 1, 2, 3) are:
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)

Example 2:

Input: s = “D”
Output: 1

Constraints:

• n == s.length
• 1 <= n <= 200
• s[i] is either ‘I’ or ‘D’.

From: LeetCode
Link: 903. Valid Permutations for DI Sequence

Solution:

Ideas:

• Rank-based DP avoids dealing with actual values 0…n; only relative order matters.

• Transitions follow the “I”/“D” constraint via ranges over previous ranks.

• Prefix sums turn each transition from O(n) to O(1), giving total O(n²) time and O(n) space.

Code:

#define MOD 1000000007

int numPermsDISequence(char* s) {
    int n = (int)strlen(s);
    // dp has size (i+1) after processing i characters of s[0..i-1]
    int dp[205] = {0}, ndp[205] = {0}, pref[205] = {0};
    dp[0] = 1;  // length 1 sequence (only one number)
    
    for (int i = 0; i < n; ++i) {
        // prefix sums of dp[0..i]
        long long run = 0;
        for (int k = 0; k <= i; ++k) {
            run += dp[k];
            if (run >= MOD) run -= MOD;
            pref[k] = (int)run;
        }

        if (s[i] == 'I') {
            // new size: i+2 (indices 0..i+1)
            for (int j = 0; j <= i + 1; ++j) {
                // sum_{k=0..j-1} dp[k]
                if (j == 0) ndp[j] = 0;
                else ndp[j] = pref[j - 1];
            }
        } else { // 'D'
            for (int j = 0; j <= i + 1; ++j) {
                // sum_{k=j..i} dp[k] = pref[i] - pref[j-1]
                long long val = pref[i];
                if (j > 0) {
                    val -= pref[j - 1];
                }
                val %= MOD;
                if (val < 0) val += MOD;
                ndp[j] = (int)val;
            }
        }

        // move ndp -> dp, clear ndp
        for (int j = 0; j <= i + 1; ++j) {
            dp[j] = ndp[j];
            ndp[j] = 0;
        }
    }

    // answer = sum of dp[0..n]
    long long ans = 0;
    for (int j = 0; j <= n; ++j) {
        ans += dp[j];
        if (ans >= MOD) ans -= MOD;
    }
    return (int)ans;
}