Valid Permutations for DI Sequence

Problem

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.

Examples

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'.

Solution

Method 1 – Dynamic Programming with Prefix Sum

Intuition

We use DP where dp[i][j] is the number of ways to fill the first i positions with j as the last number. For each position, we use prefix sums to efficiently compute the number of valid ways based on the previous character ('I' or 'D').

Approach

1. Let n = len(s). Initialize dp[0][j] = 1 for all j in [0, n].
2. For each position i from 1 to n:
   • If s[i-1] == 'I', for each j, set dp[i][j] to the sum of dp[i-1][k] for k < j.
   • If s[i-1] == 'D', for each j, set dp[i][j] to the sum of dp[i-1][k] for k >= j.
   • Use prefix sums to optimize the sum calculation.
3. The answer is the sum of dp[n][j] for all j.

Code

C++

class Solution {
public:
    int numPermsDISequence(string s) {
        int n = s.size(), mod = 1e9+7;
        vector<vector<int>> dp(n+1, vector<int>(n+1));
        for (int j = 0; j <= n; ++j) dp[0][j] = 1;
        for (int i = 1; i <= n; ++i) {
            vector<int> pre(n+2);
            for (int j = 0; j <= n; ++j) pre[j+1] = (pre[j] + dp[i-1][j]) % mod;
            for (int j = 0; j <= n; ++j) {
                if (s[i-1] == 'I') dp[i][j] = pre[j];
                else dp[i][j] = (pre[n+1] - pre[j+1] + mod) % mod;
            }
        }
        int ans = 0;
        for (int j = 0; j <= n; ++j) ans = (ans + dp[n][j]) % mod;
        return ans;
    }
};

Go

func numPermsDISequence(s string) int {
    n, mod := len(s), int(1e9+7)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = 1
    }
    for i := 1; i <= n; i++ {
        pre := make([]int, n+2)
        for j := 0; j <= n; j++ {
            pre[j+1] = (pre[j] + dp[i-1][j]) % mod
        }
        for j := 0; j <= n; j++ {
            if s[i-1] == 'I' {
                dp[i][j] = pre[j]
            } else {
                dp[i][j] = (pre[n+1] - pre[j+1] + mod) % mod
            }
        }
    }
    ans := 0
    for j := 0; j <= n; j++ {
        ans = (ans + dp[n][j]) % mod
    }
    return ans
}

Java

class Solution {
    public int numPermsDISequence(String s) {
        int n = s.length(), mod = 1000000007;
        int[][] dp = new int[n+1][n+1];
        for (int j = 0; j <= n; ++j) dp[0][j] = 1;
        for (int i = 1; i <= n; ++i) {
            int[] pre = new int[n+2];
            for (int j = 0; j <= n; ++j) pre[j+1] = (pre[j] + dp[i-1][j]) % mod;
            for (int j = 0; j <= n; ++j) {
                if (s.charAt(i-1) == 'I') dp[i][j] = pre[j];
                else dp[i][j] = (pre[n+1] - pre[j+1] + mod) % mod;
            }
        }
        int ans = 0;
        for (int j = 0; j <= n; ++j) ans = (ans + dp[n][j]) % mod;
        return ans;
    }
}

Kotlin

class Solution {
    fun numPermsDISequence(s: String): Int {
        val n = s.length
        val mod = 1000000007
        val dp = Array(n+1) { IntArray(n+1) }
        for (j in 0..n) dp[0][j] = 1
        for (i in 1..n) {
            val pre = IntArray(n+2)
            for (j in 0..n) pre[j+1] = (pre[j] + dp[i-1][j]) % mod
            for (j in 0..n) {
                dp[i][j] = if (s[i-1] == 'I') pre[j] else (pre[n+1] - pre[j+1] + mod) % mod
            }
        }
        var ans = 0
        for (j in 0..n) ans = (ans + dp[n][j]) % mod
        return ans
    }
}

Python

class Solution:
    def numPermsDISequence(self, s: str) -> int:
        n, mod = len(s), 10**9+7
        dp = [[0]*(n+1) for _ in range(n+1)]
        for j in range(n+1):
            dp[0][j] = 1
        for i in range(1, n+1):
            pre = [0]*(n+2)
            for j in range(n+1):
                pre[j+1] = (pre[j] + dp[i-1][j]) % mod
            for j in range(n+1):
                if s[i-1] == 'I':
                    dp[i][j] = pre[j]
                else:
                    dp[i][j] = (pre[n+1] - pre[j+1] + mod) % mod
        return sum(dp[n]) % mod

Rust

impl Solution {
    pub fn num_perms_di_sequence(s: String) -> i32 {
        let n = s.len();
        let modv = 1_000_000_007;
        let mut dp = vec![vec![0; n+1]; n+1];
        for j in 0..=n { dp[0][j] = 1; }
        let s = s.as_bytes();
        for i in 1..=n {
            let mut pre = vec![0; n+2];
            for j in 0..=n { pre[j+1] = (pre[j] + dp[i-1][j]) % modv; }
            for j in 0..=n {
                dp[i][j] = if s[i-1] == b'I' { pre[j] } else { (pre[n+1] - pre[j+1] + modv) % modv };
            }
        }
        dp[n].iter().fold(0, |acc, &x| (acc + x) % modv)
    }
}

TypeScript

class Solution {
    numPermsDISequence(s: string): number {
        const n = s.length, mod = 1e9+7
        const dp = Array.from({length: n+1}, () => Array(n+1).fill(0))
        for (let j = 0; j <= n; ++j) dp[0][j] = 1
        for (let i = 1; i <= n; ++i) {
            const pre = Array(n+2).fill(0)
            for (let j = 0; j <= n; ++j) pre[j+1] = (pre[j] + dp[i-1][j]) % mod
            for (let j = 0; j <= n; ++j) {
                if (s[i-1] === 'I') dp[i][j] = pre[j]
                else dp[i][j] = (pre[n+1] - pre[j+1] + mod) % mod
            }
        }
        return dp[n].reduce((a, b) => (a + b) % mod, 0)
    }
}

Complexity

• ⏰ Time complexity: O(n^2) — DP table and prefix sums.
• 🧺 Space complexity: O(n^2) — For the DP table.