problem0903

package
v0.0.0-...-d3fc627 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Feb 15, 2020 License: MIT Imports: 0 Imported by: 0

README

903. Valid Permutations for DI Sequence

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

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

Documentation

The Go Gopher

There is no documentation for this package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL