Scale Engineer

Valid Permutations for DI Sequence

Hard
#0857Time: O((n+1)!) because in the worst case, it explores all possible permutations of `n+1` numbers.Space: O(n) for the recursion stack depth and to keep track of used numbers.
Patterns
Dynamic ProgrammingPrefix Sum
Data structures
String

Prompt

You are given a string s of length n where s[i] is either:

  • 'D' means decreasing, or
  • 'I' means 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 109 + 7.

 

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

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

A naive approach is to generate every possible permutation of numbers from 0 to n, and then check if each permutation satisfies the conditions given by the string s. This is highly inefficient. A better, but still too slow, approach is to use backtracking. We can build a permutation one number at a time, and if at any step the condition is violated, we stop exploring that path (pruning).

Algorithm

  • Create a recursive function, say countValidPermutations(currentPermutation, usedNumbers).
  • The base case: if the currentPermutation has length n + 1, we have found one valid permutation, so return 1.
  • In the recursive step, iterate through all numbers num from 0 to n.
  • If num has not been used yet:
    • Add num to the currentPermutation.
    • Before recursing, check if the new partial permutation is valid. If currentPermutation has at least two elements, check currentPermutation[k-1] and currentPermutation[k] against s[k-1].
    • If it's valid, call the function recursively and add the result to a running total.
    • Backtrack: remove num from the permutation and mark it as unused to explore other possibilities.
  • The total count is the sum of results from all valid recursive calls.

Walkthrough

We define a recursive function that tries to place an unused number at the next position in the permutation. The function keeps track of the permutation being built and which numbers from [0, n] have already been used. At each step, we try to append an unused number. If the new number maintains the validity of the permutation according to the DI sequence, we proceed recursively. If not, we prune this path and try another number. When a full permutation of length n+1 is formed, we count it as one valid permutation.

Complexity

Time

O((n+1)!) because in the worst case, it explores all possible permutations of `n+1` numbers.

Space

O(n) for the recursion stack depth and to keep track of used numbers.

Trade-offs

Pros

  • Conceptually simple to understand.

  • Correct for very small inputs.

Cons

  • Extremely high time complexity, making it infeasible for the given constraints.

  • Will result in a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution {public  int numPermsDISequence(String s) {    final int mod = (int)1 e9 + 7;    int n = s.length();    int[] f = new int[n + 1];    f[0] = 1;    for (int i = 1; i <= n; ++i) {      int pre = 0;      int[] g = new int[n + 1];      if (s.charAt(i - 1) == 'D') {        for (int j = i; j >= 0; --j) {          pre = (pre + f[j]) % mod;          g[j] = pre;        }      } else {        for (int j = 0; j <= i; ++j) {          g[j] = pre;          pre = (pre + f[j]) % mod;        }      }      f = g;    }    int ans = 0;    for (int j = 0; j <= n; ++j) {      ans = (ans + f[j]) % mod;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem