Algorithm

Problem Name: 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 `109 + 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'`

Code Examples

#1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numPermsDISequence = function(s) {
const mod = 1e9 + 7
const n = s.length
const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0))
s = '#' + s
dp[0][0] = 1
for(let i = 1; i  < = n; i++) {
const ch = s[i]
for(let j = 0; j  < = i; j++) {
if(ch === 'I') {
for(let k = 0; k < j; k++) {
dp[i][j] += dp[i - 1][k]
dp[i][j] %= mod
}
} else {
for(let k = j; k  <  i; k++) {
dp[i][j] += dp[i - 1][k]
dp[i][j] %= mod
}
}
}
}

let res = 0

for(let i = 0; i  < = n; i++) {
res = (res + dp[n][i]> % mod
}

return res
};
``````
Copy The Code &

Input

cmd
s = "DID"

Output

cmd
5

#2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def numPermsDISequence(self, S: str) -> int:
dp = [1] * (len(S) + 1)
for c in S:
if c == "I":
dp = dp[:-1]
for i in range(1, len(dp)):
dp[i] += dp[i - 1]
else:
dp = dp[1:]
for i in range(len(dp) - 1)[::-1]:
dp[i] += dp[i + 1]
return dp[0] % (10**9 + 7)
``````
Copy The Code &

Input

cmd
s = "DID"

Output

cmd
5