GeetCode Hub

We are given s, a length n string of characters from the set {'D', 'I'}. (These letters stand for "decreasing" and "increasing".)

valid permutation is a permutation p[0], p[1], ..., p[n] of integers {0, 1, ..., n}, such that for all i:

  • If s[i] == 'D', then p[i] > p[i+1], and;
  • If s[i] == 'I', then p[i] < p[i+1].

How many valid permutations are there?  Since the answer may be large, return your answer 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)

 

Note:

  1. 1 <= s.length <= 200
  2. s consists only of characters from the set {'D', 'I'}.

 

class Solution { public int numPermsDISequence(String s) { } }