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

Let n = len(s). Initialize dp[0][j] = 1 for all j in [0, n].
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.
The answer is the sum of dp[n][j] for all j.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int numPermsDISequence(string s) {\n        int n = s.size(), mod = 1e9+7;\n        vector<vector<int>> dp(n+1, vector<int>(n+1));\n        for (int j = 0; j <= n; ++j) dp[0][j] = 1;\n        for (int i = 1; i <= n; ++i) {\n            vector<int> pre(n+2);\n            for (int j = 0; j <= n; ++j) pre[j+1] = (pre[j] + dp[i-1][j]) % mod;\n            for (int j = 0; j <= n; ++j) {\n                if (s[i-1] == 'I') dp[i][j] = pre[j];\n                else dp[i][j] = (pre[n+1] - pre[j+1] + mod) % mod;\n            }\n        }\n        int ans = 0;\n        for (int j = 0; j <= n; ++j) ans = (ans + dp[n][j]) % mod;\n        return ans;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func numPermsDISequence(s string) int {\n    n, mod := len(s), int(1e9+7)\n    dp := make([][]int, n+1)\n    for i := range dp {\n        dp[i] = make([]int, n+1)\n    }\n    for j := 0; j <= n; j++ {\n        dp[0][j] = 1\n    }\n    for i := 1; i <= n; i++ {\n        pre := make([]int, n+2)\n        for j := 0; j <= n; j++ {\n            pre[j+1] = (pre[j] + dp[i-1][j]) % mod\n        }\n        for j := 0; j <= n; j++ {\n            if s[i-1] == 'I' {\n                dp[i][j] = pre[j]\n            } else {\n                dp[i][j] = (pre[n+1] - pre[j+1] + mod) % mod\n            }\n        }\n    }\n    ans := 0\n    for j := 0; j <= n; j++ {\n        ans = (ans + dp[n][j]) % mod\n    }\n    return ans\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int numPermsDISequence(String s) {\n        int n = s.length(), mod = 1000000007;\n        int[][] dp = new int[n+1][n+1];\n        for (int j = 0; j <= n; ++j) dp[0][j] = 1;\n        for (int i = 1; i <= n; ++i) {\n            int[] pre = new int[n+2];\n            for (int j = 0; j <= n; ++j) pre[j+1] = (pre[j] + dp[i-1][j]) % mod;\n            for (int j = 0; j <= n; ++j) {\n                if (s.charAt(i-1) == 'I') dp[i][j] = pre[j];\n                else dp[i][j] = (pre[n+1] - pre[j+1] + mod) % mod;\n            }\n        }\n        int ans = 0;\n        for (int j = 0; j <= n; ++j) ans = (ans + dp[n][j]) % mod;\n        return ans;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun numPermsDISequence(s: String): Int {\n        val n = s.length\n        val mod = 1000000007\n        val dp = Array(n+1) { IntArray(n+1) }\n        for (j in 0..n) dp[0][j] = 1\n        for (i in 1..n) {\n            val pre = IntArray(n+2)\n            for (j in 0..n) pre[j+1] = (pre[j] + dp[i-1][j]) % mod\n            for (j in 0..n) {\n                dp[i][j] = if (s[i-1] == 'I') pre[j] else (pre[n+1] - pre[j+1] + mod) % mod\n            }\n        }\n        var ans = 0\n        for (j in 0..n) ans = (ans + dp[n][j]) % mod\n        return ans\n    }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def numPermsDISeq

Related Tags