#903

Valid Permutations for DI Sequence

expert · 1270 · lc hard +32 · verified · 56.3% accepted · 751 likes · top 50%

Description

You are given a string s of length n where each character is 'D' (must decrease) or 'I' (must increase). Count permutations of the integers [0, n] in which each adjacent pair satisfies the corresponding constraint from s. Return the answer modulo 10⁹ + 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

Code

1

2

3

class Solution:
    def numPermsDISequence(self, s: str) -> int:

class Solution:
    def numPermsDISequence(self, s: str) -> int: