# LeetCode 903: Valid Permutations for DI Sequence

## Problem Restatement

We are given a string `s` of length `n`.

Each character is either:

| Character | Meaning |
|---|---|
| `"I"` | Increasing |
| `"D"` | Decreasing |

We need to count how many permutations of the integers from `0` to `n` satisfy the pattern.

A permutation has `n + 1` numbers.

For every index `i`:

- If `s[i] == "I"`, then `perm[i] < perm[i + 1]`.
- If `s[i] == "D"`, then `perm[i] > perm[i + 1]`.

Return the answer modulo:

```python
10**9 + 7
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` containing only `"I"` and `"D"` |
| Output | Number of valid permutations |
| Numbers used | All integers from `0` to `n` |
| Modulo | `10^9 + 7` |

Function shape:

```python
def numPermsDISequence(s: str) -> int:
    ...
```

## Examples

Example:

```python
s = "DID"
```

We need a permutation of:

```python
[0, 1, 2, 3]
```

The pattern means:

```python
perm[0] > perm[1] < perm[2] > perm[3]
```

There are `5` valid permutations:

```python
[1, 0, 3, 2]
[2, 0, 3, 1]
[2, 1, 3, 0]
[3, 0, 2, 1]
[3, 1, 2, 0]
```

So the answer is:

```python
5
```

## First Thought: Generate All Permutations

The direct method is to generate every permutation of `0..n`, then check whether it satisfies the pattern.

```python
from itertools import permutations

class Solution:
    def numPermsDISequence(self, s: str) -> int:
        n = len(s)
        answer = 0

        for perm in permutations(range(n + 1)):
            valid = True

            for i, ch in enumerate(s):
                if ch == "I" and perm[i] >= perm[i + 1]:
                    valid = False
                    break
                if ch == "D" and perm[i] <= perm[i + 1]:
                    valid = False
                    break

            if valid:
                answer += 1

        return answer
```

This is useful for understanding the problem, but it is far too slow.

There are `(n + 1)!` permutations.

## Key Insight

The actual values do not matter as much as their relative order.

For example, among three chosen numbers, the smallest has rank `0`, the next has rank `1`, and the largest has rank `2`.

Dynamic programming can count valid partial permutations by tracking the rank of the last chosen number.

Let:

```python
dp[j]
```

mean:

After building a valid sequence of length `i + 1`, the last number has rank `j` among the remaining possible relative ranks.

A simpler way to read it:

At each length, `dp[j]` counts valid partial sequences whose last element is the `j`-th smallest among the numbers used so far.

We do not need the exact values. We only need how many choices are smaller or greater.

## DP Transition

Suppose we have already processed `i` numbers.

Now we use the next character `s[i - 1]`.

There are two cases.

### Case 1: Current Pattern Is `"I"`

We need:

```python
previous < current
```

If the current rank is `j`, then the previous rank must be smaller than `j`.

So:

```python
new_dp[j] = dp[0] + dp[1] + ... + dp[j - 1]
```

### Case 2: Current Pattern Is `"D"`

We need:

```python
previous > current
```

If the current rank is `j`, then the previous rank must be at least `j`.

So:

```python
new_dp[j] = dp[j] + dp[j + 1] + ... + dp[i - 1]
```

These sums can be computed efficiently with prefix sums.

## Algorithm

Let `n = len(s)`.

Start with one number. There is exactly one way to arrange one number:

```python
dp = [1]
```

Then process characters from left to right.

For each character, build a new DP array of length one larger.

If the character is `"I"`:

- Use prefix sums from left to right.
- `new_dp[j]` gets the sum of all previous states before `j`.

If the character is `"D"`:

- Use suffix sums from right to left.
- `new_dp[j]` gets the sum of all previous states from `j` onward.

At the end, sum all values in `dp`.

## Correctness

The DP state records enough information because future comparisons only care whether the next number is larger or smaller than the previous number.

For a partial sequence, the exact labels of the used numbers are irrelevant. Only the relative rank of the last number matters.

When the next character is `"I"`, the next number must be greater than the previous number. For a chosen current rank `j`, all previous ranks smaller than `j` are valid, and all previous ranks greater than or equal to `j` are invalid.

When the next character is `"D"`, the next number must be smaller than the previous number. For a chosen current rank `j`, all previous ranks greater than or equal to `j` are valid, and all previous ranks smaller than `j` are invalid.

The transition counts exactly these valid choices.

After all `n` characters are processed, every DP state represents a valid permutation satisfying the whole string. Summing the states gives the total number of valid permutations.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | Each of `n` steps computes an array of size up to `n` |
| Space | `O(n)` | Only the current DP row is stored |

## Implementation

```python
class Solution:
    def numPermsDISequence(self, s: str) -> int:
        MOD = 10**9 + 7

        dp = [1]

        for ch in s:
            m = len(dp)
            new_dp = [0] * (m + 1)

            if ch == "I":
                prefix = 0

                for j in range(m + 1):
                    if j > 0:
                        prefix = (prefix + dp[j - 1]) % MOD
                    new_dp[j] = prefix

            else:
                suffix = 0

                for j in range(m - 1, -1, -1):
                    suffix = (suffix + dp[j]) % MOD
                    new_dp[j] = suffix

            dp = new_dp

        return sum(dp) % MOD
```

## Code Explanation

We start with:

```python
dp = [1]
```

There is one valid sequence of length `1`.

For each new pattern character, the sequence length increases by one, so the new DP array has one extra slot:

```python
new_dp = [0] * (m + 1)
```

For `"I"`, the current value must be greater than the previous value.

So each state takes the sum of previous ranks smaller than it:

```python
if ch == "I":
    prefix = 0

    for j in range(m + 1):
        if j > 0:
            prefix = (prefix + dp[j - 1]) % MOD
        new_dp[j] = prefix
```

For `"D"`, the current value must be smaller than the previous value.

So each state takes the sum of previous ranks greater than or equal to it:

```python
else:
    suffix = 0

    for j in range(m - 1, -1, -1):
        suffix = (suffix + dp[j]) % MOD
        new_dp[j] = suffix
```

At the end, every state is a valid complete permutation:

```python
return sum(dp) % MOD
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numPermsDISequence("DID") == 5
    assert s.numPermsDISequence("I") == 1
    assert s.numPermsDISequence("D") == 1
    assert s.numPermsDISequence("II") == 1
    assert s.numPermsDISequence("DD") == 1
    assert s.numPermsDISequence("ID") == 2
    assert s.numPermsDISequence("DI") == 2

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"DID"` | Main sample case |
| `"I"` | Smallest increasing case |
| `"D"` | Smallest decreasing case |
| `"II"` | Only sorted increasing order works |
| `"DD"` | Only sorted decreasing order works |
| `"ID"` | Peak shape |
| `"DI"` | Valley shape |