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’).
classSolution {
publicintnumPermsDISequence(String s) {
int n = s.length(), mod = 1000000007;
int[][] dp =newint[n+1][n+1];
for (int j = 0; j <= n; ++j) dp[0][j]= 1;
for (int i = 1; i <= n; ++i) {
int[] pre =newint[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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
funnumPermsDISequence(s: String): Int {
val n = s.length
val mod = 1000000007val dp = Array(n+1) { IntArray(n+1) }
for (j in0..n) dp[0][j] = 1for (i in1..n) {
val pre = IntArray(n+2)
for (j in0..n) pre[j+1] = (pre[j] + dp[i-1][j]) % mod
for (j in0..n) {
dp[i][j] = if (s[i-1] =='I') pre[j] else (pre[n+1] - pre[j+1] + mod) % mod
}
}
var ans = 0for (j in0..n) ans = (ans + dp[n][j]) % mod
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution:
defnumPermsDISequence(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] =1for 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
pubfnnum_perms_di_sequence(s: String) -> i32 {
let n = s.len();
let modv =1_000_000_007;
letmut dp =vec![vec![0; n+1]; n+1];
for j in0..=n { dp[0][j] =1; }
let s = s.as_bytes();
for i in1..=n {
letmut pre =vec![0; n+2];
for j in0..=n { pre[j+1] = (pre[j] + dp[i-1][j]) % modv; }
for j in0..=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)
}
}