Valid Permutations for DI Sequence — LeetCode 903 Python Solution

The 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].

Example

Input

s = "DID"

Output

5

Explanation

The 5 valid permutations of (0, 1, 2, 3) are:

Python solution

class Solution:
    def numPermsDISequence(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        f = [[0] * (n + 1) for _ in range(n + 1)]
        f[0][0] = 1
        for i, c in enumerate(s, 1):
            if c == "D":
                for j in range(i + 1):
                    for k in range(j, i):
                        f[i][j] = (f[i][j] + f[i - 1][k]) % mod
            else:
                for j in range(i + 1):
                    for k in range(j):
                        f[i][j] = (f[i][j] + f[i - 1][k]) % mod
        return sum(f[n][j] for j in range(n + 1)) % mod

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 903. Valid Permutations for DI Sequence is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems