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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Valid Permutations for DI Sequence and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →