README_EN.md

903. Valid Permutations for DI Sequence

中文文档

Description

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

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

<li>If <code>S[i] == &#39;D&#39;</code>, then <code>P[i] &gt; P[i+1]</code>, and;</li>

<li>If <code>S[i] == &#39;I&#39;</code>, then <code>P[i] &lt; P[i+1]</code>.</li>

How many valid permutations are there?  Since the answer may be large, return your answer modulo 10^9 + 7.

 

Example 1:

Input: "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:

<li><code>1 &lt;= S.length &lt;= 200</code></li>

<li><code>S</code> consists only of characters from the set <code>{&#39;D&#39;, &#39;I&#39;}</code>.</li>

 

Solutions

Python3

Java

...