Skip to main content

903. Valid Permutations for DI Sequence

hard

Count permutations of 0..n that follow a D/I (decrease/increase) string. A 1D-prefix-sum DP that drops the naive O(n^3) to O(n^2).

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 consists only of characters 'I' and '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

Let dp[i][j] = number of valid permutations of length i+1 ending with the j-th smallest of the remaining values.

Hint 2

For 'I' at position i, dp[i+1][j] = sum over k <= j of dp[i][k]. For 'D', sum over k > j.

Hint 3

Replace the inner sum with prefix sums to drop O(n^3) to O(n^2).

Solution approach

Reveal approach

Define dp[i][j] as the count of valid prefixes of length i+1 that end with the j-th smallest among the values still available to place (relative ranking insight). For s[i] = 'I' (next must be larger), dp[i+1][j] = sum over k from 0 to j-1 of dp[i][k]. For s[i] = 'D', dp[i+1][j] = sum over k from j to i of dp[i][k]. Naive triple loop is O(n^3); replace the inner sum with a prefix-sum scan to get O(n^2). Initialize dp[0][0] = 1. The final answer is sum over j of dp[n][j] modulo 10^9 + 7. The relative-rank framing avoids tracking the actual value set, which is the key insight.

Complexity

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

Related patterns

  • dynamic-programming
  • prefix-sum

Related problems

Asked at

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

  • Google

More DP 1D practice problems

See all DP 1D problems →