Skip to main content

903. Valid Permutations for DI Sequence

hard

Count permutations of 0..n that follow a given pattern of 'D' (decrease) and 'I' (increase). 2D DP where dp[i][j] = ways to form the first i+1 elements ending at the j-th smallest unused number.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given a string s of length n where s[i] is either: 'D' meaning decreasing, or 'I' meaning 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]. Return the number of valid permutations perm. Since the answer may be large, return it modulo 10^9 + 7.

Constraints

  • n == s.length
  • 1 <= n <= 200
  • s[i] is either 'I' or 'D'.

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i][j] = number of valid permutations of length i+1 where perm[i] is the j-th smallest of the i+1 numbers used so far.

Hint 2

If s[i-1] == 'I': perm[i] > perm[i-1], so dp[i][j] = sum_{k < j} dp[i-1][k]. (Choose any predecessor rank less than j.)

Hint 3

If s[i-1] == 'D': perm[i] < perm[i-1], so dp[i][j] = sum_{k >= j} dp[i-1][k]. (Predecessor must be rank j or larger after re-indexing.)

Hint 4

Maintain prefix sums of the previous row to keep transitions O(1). Total time O(n^2).

Solution approach

Reveal approach

Bottom-up 2D DP indexed by (length, rank of last element among the length+1 numbers used so far). dp[i][j] is the count of valid permutations of length i + 1 with the last element being the j-th smallest of the i + 1 distinct numbers (0..i seen in some order). Base: dp[0][0] = 1 — a length-1 permutation is just one number, rank 0. Transition: if s[i-1] == 'I', the new last element must be greater than the previous, so dp[i][j] = sum over k = 0..j-1 of dp[i-1][k]. If s[i-1] == 'D', it must be smaller, so dp[i][j] = sum over k = j..i-1 of dp[i-1][k] (the previous rank shifts because a new number is inserted). Maintain prefix sums of the previous row so each transition is O(1). Answer: sum over j = 0..n of dp[n][j], mod 10^9 + 7.

Complexity

Time
O(n^2)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • string-dp
  • prefix-sum

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →