LeetCode 903: Valid Permutations for DI Sequence

Problem Restatement

We are given a string s of length n.

Each character is either:

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:

10**9 + 7

Input and Output

Function shape:

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

Examples

Example:

s = "DID"

We need a permutation of:

[0, 1, 2, 3]

The pattern means:

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

There are 5 valid permutations:

[1, 0, 3, 2]
[2, 0, 3, 1]
[2, 1, 3, 0]
[3, 0, 2, 1]
[3, 1, 2, 0]

So the answer is:

5

First Thought: Generate All Permutations

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

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:

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:

previous < current

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

So:

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

Case 2: Current Pattern Is "D"

We need:

previous > current

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

So:

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:

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

Implementation

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:

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:

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:

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:

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:

return sum(dp) % MOD

Testing

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: