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

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →