# Valid Permutations for DI Sequence
**Difficulty:** HARD
[External](https://leetcode.com/problems/valid-permutations-for-di-sequence)
Canonical: https://scaleengineer.com/dsa/problems/valid-permutations-for-di-sequence
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** String
---
## Problem
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
## Brute-force via Backtracking
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).
**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.
**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.
### Explanation
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.
### 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.

## Dynamic Programming (O(N³))
Since the backtracking approach is too slow, we can look for overlapping subproblems and optimal substructure, which suggests dynamic programming. We can define a DP state based on the length of the permutation being built and the value of the last element.
**Time:** O(N³) due to three nested loops (i, j, and k for the sum). · **Space:** O(N²) for the DP table.
**Pros:** Significantly more efficient than backtracking.; Solves the problem for moderate values of n.
**Cons:** The O(N³) complexity might be too slow if n was larger.; Uses O(N²) space which can be improved.
### Explanation
Let `dp[i][j]` be the number of valid permutations for the prefix `s[0...i-1]` (of length `i`) using the numbers `{0, 1, ..., i}` where the last element of the permutation is `j`. The key insight is that the absolute values of numbers don't matter as much as their relative order. When we transition from a permutation of `{0,...,i-1}` to one of `{0,...,i}`, we are essentially inserting a new number and re-labeling the existing ones to maintain their relative order. This leads to a recurrence relation where `dp[i][j]` is calculated by summing up certain values from the `dp[i-1]` row. The specific range of the sum depends on whether `s[i-1]` is 'I' or 'D'.
### Algorithm
- Create a 2D array `dp[n+1][n+1]`.
- Base case: For a length 1 permutation of `{0}`, there's only one possibility: `(0)`. So, `dp[0][0] = 1`.
- Iterate `i` from 1 to `n` (for `s[0...i-1]`).
  - Iterate `j` from 0 to `i` (the last element of the new permutation).
    - If `s[i-1] == 'I'`, we need `perm[i-1] < perm[i]`. This means the last element of the previous permutation (after re-labeling) must be smaller than `j`. This is possible if the original last element `k` was less than `j`. So, `dp[i][j] = sum(dp[i-1][k] for k from 0 to j-1)`.
    - If `s[i-1] == 'D'`, we need `perm[i-1] > perm[i]`. This means the last element of the previous permutation (after re-labeling) must be larger than `j`. This is possible if the original last element `k` was greater than or equal to `j`. So, `dp[i][j] = sum(dp[i-1][k] for k from j to i-1)`.
- The final answer is the sum of all values in the last row `dp[n]`.

## Optimized Dynamic Programming (O(N²))
The `O(N³)` DP approach can be optimized. The calculation for each `dp[i][j]` involves summing up a range of values from the previous row `dp[i-1]`. These are essentially prefix sums or suffix sums. We can compute these sums more efficiently.
**Time:** O(N²) due to the two nested loops. The outer loop runs `n` times, and the inner loop runs `i+1` times, where `i` goes up to `n`. · **Space:** O(N) with space optimization, as we only need to store the DP values for the previous length to compute the current one. Without this optimization, it would be O(N²).
**Pros:** Optimal time complexity that passes the given constraints.; Space can be optimized to O(N).
**Cons:** The DP state and transitions are clever and might not be immediately obvious.
### Explanation
Instead of re-calculating the sum in an inner loop every time, we can calculate the new DP row `dp[i]` based on `dp[i-1]` in a single pass.
- If `s[i-1] == 'I'`, `dp[i][j]` is the prefix sum `dp[i-1][0] + ... + dp[i-1][j-1]`. We can compute this for all `j` by maintaining a running sum as we iterate through `j`.
- If `s[i-1] == 'D'`, `dp[i][j]` is the suffix sum `dp[i-1][j] + ... + dp[i-1][i-1]`. We can compute this for all `j` by iterating backwards and maintaining a running sum.
This optimization reduces the time complexity to `O(N²)`. Furthermore, since `dp[i]` only depends on `dp[i-1]`, we can optimize space to `O(N)` by only storing the current and previous DP rows.
```java
class Solution {
    public int numPermsDISequence(String s) {
        int n = s.length();
        int MOD = 1_000_000_007;
        
        // dp[j] represents the number of valid permutations for the prefix of s of length i-1,
        // using numbers {0, ..., i-1}, ending with j.
        int[] dp = new int[1];
        dp[0] = 1; // Base case: i=0, s="", perm of {0} is (0).

        for (int i = 1; i <= n; i++) {
            int[] newDp = new int[i + 1];
            if (s.charAt(i - 1) == 'I') {
                int currentSum = 0;
                for (int j = 0; j <= i; j++) {
                    newDp[j] = currentSum;
                    if (j < i) { // dp is from prev iteration, has i elements (0 to i-1)
                        currentSum = (currentSum + dp[j]) % MOD;
                    }
                }
            } else { // s.charAt(i - 1) == 'D'
                int currentSum = 0;
                for (int j = i; j >= 0; j--) {
                    newDp[j] = currentSum;
                    if (j > 0) { // dp has i elements, need to access dp[j-1]
                        currentSum = (currentSum + dp[j - 1]) % MOD;
                    }
                }
            }
            dp = newDp;
        }

        long total = 0;
        for (int count : dp) {
            total = (total + count) % MOD;
        }
        
        return (int) total;
    }
}
```
### Algorithm
- Initialize a 1D `dp` array `dp = [1]`, representing the base case for a permutation of length 1.
- Loop `i` from 1 to `n`. In each iteration, `dp` holds the values for permutations of length `i`, and we compute `newDp` for permutations of length `i+1`.
  - Create a `newDp` array of size `i+1`.
  - If `s[i-1] == 'I'`:
    - Initialize `currentSum = 0`.
    - Iterate `j` from 0 to `i`. Set `newDp[j] = currentSum`, then update `currentSum` by adding `dp[j]` (from the previous iteration's array).
  - If `s[i-1] == 'D'`:
    - Initialize `currentSum = 0`.
    - Iterate `j` from `i` down to 0. Set `newDp[j] = currentSum`, then update `currentSum` by adding `dp[j-1]`.
  - Replace `dp` with `newDp` for the next iteration.
- After the loop, sum all elements in the final `dp` array to get the total count.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numPermsDISequence(string s) {
    const int mod = 1e9 + 7;
    int n = s.size();
    vector<int> f(n + 1);
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
      int pre = 0;
      vector<int> g(n + 1);
      if (s[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 = move(g);
    }
    int ans = 0;
    for (int j = 0; j <= n; ++j) {
      ans = (ans + f[j]) % mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numPermsDISequence(self, s: str) -> int: mod = 10 ** 9 + 7 n = len(s) f = [1] + [0] * n for i, c in enumerate(s, 1): pre = 0 g = [0] * (n + 1) if c == "D": for j in range(i, - 1, - 1): pre = (pre + f[j]) % mod g[j] = pre else: for j in range(i + 1): g[j] = pre pre = (pre + f[j]) % mod f = g return sum(f) % mod

```