LeetCode 903 - Valid Permutations for DI Sequence

LeetCode Problem 903

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming, Prefix Sum

Solution

Problem Understanding

The problem gives us a string s of length n, where each character describes the relationship between two adjacent elements in a permutation.

The permutation must contain every integer from 0 to n exactly once, so the permutation length is always n + 1.

Each character in the string imposes a constraint:

• 'I' means the next number must be larger than the current one.
• 'D' means the next number must be smaller than the current one.

For example, if s = "DID", then the permutation must satisfy:

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

We are asked to count how many valid permutations satisfy all these conditions.

The important detail is that we only need the count, not the permutations themselves. Since the number of permutations grows extremely quickly, the answer can become very large, so we return it modulo 10^9 + 7.

The constraints are especially important:

• n <= 200

A permutation of length 201 has 201! possible arrangements, which is astronomically large. Any brute force enumeration is completely infeasible. This strongly suggests that the solution must use dynamic programming and exploit structure in the constraints.

Several edge cases are important:

• A string consisting entirely of 'I', such as "III", only allows strictly increasing permutations.
• A string consisting entirely of 'D', such as "DDD", only allows strictly decreasing permutations.
• Alternating patterns like "DIDID" create many branching possibilities.
• Since the answer is modulo 10^9 + 7, every arithmetic operation must carefully apply modulo reduction.

Approaches

Brute Force Approach

The most direct solution is to generate every permutation of numbers from 0 to n and check whether it satisfies the DI constraints.

For each permutation:

1. Iterate through the string s.
2. If s[i] == 'I', verify perm[i] < perm[i + 1].
3. If s[i] == 'D', verify perm[i] > perm[i + 1].
4. Count every permutation that satisfies all constraints.

This approach is correct because it explicitly checks every possible permutation. However, it is far too slow.

There are (n + 1)! permutations. Even for n = 10, this is already millions of possibilities. For n = 200, brute force is impossible.

Optimal Dynamic Programming Approach

The key insight is that we do not need the exact values used so far. We only need the relative ordering information.

Instead of constructing actual permutations, we build them incrementally and track the rank of the last chosen number among the remaining candidates.

Define:

• dp[i][j] as the number of valid ways to build a sequence of length i + 1,
• where the last element has rank j among the unused numbers.

At each step:

• If the next relation is 'I', the next rank must be larger.
• If the next relation is 'D', the next rank must be smaller.

A naive transition would require nested summations, leading to O(n^3) complexity. Since n = 200, this may still pass in optimized languages, but we can do better.

The important optimization is to use prefix sums.

For each row of DP:

• If we need sums over smaller indices, use prefix sums from left to right.
• If we need sums over larger indices, use suffix-style accumulation from right to left.

This reduces the total complexity to O(n^2).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((n + 1)! * n)	O(n)	Generates every permutation and validates it
Optimal Dynamic Programming	O(n^2)	O(n)	Uses rank-based DP with prefix sum optimization

Algorithm Walkthrough

1. Let n = len(s).

The permutation length is n + 1. 2. Initialize a DP array.

We use a one-dimensional DP array where:

• dp[j] represents the number of valid sequences for the current length,
• with the last chosen number having relative rank j.

Initially:

dp = [1]

This represents a sequence of length 1, where only one rank exists. 3. Process the string one character at a time.

For each position i:

• We are extending sequences from length i + 1 to length i + 2.
• The new DP row will contain i + 2 states.

4. Handle the 'I' case.

If s[i] == 'I', then the next rank must be greater.

For every possible new rank j:

• Valid previous ranks are all ranks smaller than j.

So:

new_dp[j] = sum(dp[0:j])

Instead of recomputing sums repeatedly, maintain a running prefix sum. 5. Handle the 'D' case.

If s[i] == 'D', then the next rank must be smaller.

For every possible new rank j:

• Valid previous ranks are all ranks greater than or equal to j.

So:

new_dp[j] = sum(dp[j:])

Use a reverse running sum to compute these efficiently. 6. Replace the current DP row.

After computing all transitions:

dp = new_dp

7. After processing all characters, sum all remaining states.

Every remaining state corresponds to a valid permutation. 8. Return the result modulo 10^9 + 7.

Why it works

The DP state stores only relative rank information, not exact numbers. This works because the DI constraints depend only on comparisons between neighboring elements.

At every step, the algorithm correctly counts all ways to extend smaller valid sequences into larger valid sequences while preserving the required ordering relationship.

The prefix sum optimization does not change the recurrence relation. It only computes repeated range sums more efficiently.

Python Solution

class Solution:
    def numPermsDISequence(self, s: str) -> int:
        MOD = 10**9 + 7
        
        dp = [1]
        
        for i, ch in enumerate(s):
            new_dp = [0] * (i + 2)
            
            if ch == 'I':
                prefix = 0
                
                for j in range(i + 1):
                    prefix = (prefix + dp[j]) % MOD
                    new_dp[j + 1] = prefix
            
            else:
                suffix = 0
                
                for j in range(i, -1, -1):
                    suffix = (suffix + dp[j]) % MOD
                    new_dp[j] = suffix
            
            dp = new_dp
        
        return sum(dp) % MOD

The implementation begins with a single valid sequence of length 1.

For each character in the input string, we construct the next DP row.

When the character is 'I', we accumulate prefix sums from left to right. Each new rank can only come from smaller previous ranks.

When the character is 'D', we accumulate suffix sums from right to left. Each new rank can only come from larger previous ranks.

The modulo operation is applied during every update to prevent overflow and satisfy the problem requirement.

At the end, every state in the final DP array corresponds to a valid permutation, so we sum all entries.

Go Solution

func numPermsDISequence(s string) int {
    const MOD int = 1_000_000_007

    dp := []int{1}

    for i, ch := range s {
        newDp := make([]int, i+2)

        if ch == 'I' {
            prefix := 0

            for j := 0; j <= i; j++ {
                prefix = (prefix + dp[j]) % MOD
                newDp[j+1] = prefix
            }
        } else {
            suffix := 0

            for j := i; j >= 0; j-- {
                suffix = (suffix + dp[j]) % MOD
                newDp[j] = suffix
            }
        }

        dp = newDp
    }

    result := 0

    for _, value := range dp {
        result = (result + value) % MOD
    }

    return result
}

The Go implementation follows exactly the same logic as the Python version.

Slices are used instead of dynamic Python lists. Since Go integers can overflow on some platforms, every arithmetic update applies modulo reduction immediately.

The DP arrays are recreated for each iteration because each row has a different size.

Worked Examples

Example 1

s = "DID"

We process the string step by step.

Initial state:

Step	DP
Start	[1]

Process 'D'

We need decreasing order.

Compute suffix sums:

j	suffix	new_dp
0	1	[1, 0]

Result:

dp = [1, 0]

Process 'I'

We need increasing order.

Compute prefix sums:

j	prefix	new_dp
0	1	[0, 1, 0]
1	1	[0, 1, 1]

Result:

dp = [0, 1, 1]

Process 'D'

We need decreasing order.

Compute suffix sums:

j	suffix	new_dp
2	1	[0, 0, 1, 0]
1	2	[0, 2, 1, 0]
0	2	[2, 2, 1, 0]

Final state:

dp = [2, 2, 1, 0]

Total:

2 + 2 + 1 + 0 = 5

Answer:

5

Example 2

s = "D"

Initial:

dp = [1]

Process 'D':

j	suffix	new_dp
0	1	[1, 0]

Final:

dp = [1, 0]

Sum:

1

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Each DP row processes at most n states
Space	O(n)	Only the current DP row is stored

The DP table conceptually has O(n^2) states, but we only keep one row at a time, reducing space usage to linear complexity.

The prefix sum optimization ensures each row is processed in linear time instead of quadratic time, giving an overall O(n^2) runtime.

Test Cases

sol = Solution()

assert sol.numPermsDISequence("D") == 1  # single decreasing relation
assert sol.numPermsDISequence("I") == 1  # single increasing relation

assert sol.numPermsDISequence("DI") == 2  # mixed short pattern
assert sol.numPermsDISequence("ID") == 2  # alternating short pattern

assert sol.numPermsDISequence("DID") == 5  # provided example

assert sol.numPermsDISequence("III") == 1  # only strictly increasing permutation
assert sol.numPermsDISequence("DDD") == 1  # only strictly decreasing permutation

assert sol.numPermsDISequence("IID") == 3  # increasing then decreasing
assert sol.numPermsDISequence("DDI") == 3  # decreasing then increasing

assert sol.numPermsDISequence("IDID") == 16  # alternating pattern
assert sol.numPermsDISequence("DIDI") == 16  # alternating pattern starting with D

assert sol.numPermsDISequence("IIIIIIII") == 1  # long all-increasing case
assert sol.numPermsDISequence("DDDDDDDD") == 1  # long all-decreasing case

Test	Why
"D"	Smallest decreasing case
"I"	Smallest increasing case
"DI"	Simple mixed ordering
"ID"	Opposite mixed ordering
"DID"	Official example
"III"	Only one strictly increasing permutation exists
"DDD"	Only one strictly decreasing permutation exists
"IID"	Tests transition from increasing to decreasing
"DDI"	Tests transition from decreasing to increasing
"IDID"	Alternating constraints
"DIDI"	Alternating constraints starting with decreasing
"IIIIIIII"	Stress test for monotonic increasing
"DDDDDDDD"	Stress test for monotonic decreasing

Edge Cases

One important edge case is when the string contains only 'I' characters. In this situation, the permutation must be strictly increasing. There is only one valid permutation, namely [0, 1, 2, ..., n]. A buggy implementation might accidentally overcount because many DP states appear reachable. The prefix sum transitions correctly preserve only one valid ordering.

Another important edge case is when the string contains only 'D' characters. Here, the permutation must be strictly decreasing, so only [n, n-1, ..., 0] is valid. This case heavily exercises the suffix sum logic. If the reverse accumulation is implemented incorrectly, this case usually fails immediately.

Alternating patterns such as "DIDIDID" are another common source of bugs. These patterns generate many branching possibilities and require transitions in both directions repeatedly. Incorrect DP indexing often appears here because the valid ranges shift every iteration. The implementation handles this correctly by carefully matching prefix sums with 'I' and suffix sums with 'D'.

A final subtle edge case involves modulo arithmetic. The number of valid permutations grows rapidly for longer strings. Without applying modulo reduction during intermediate computations, integer overflow may occur in languages like Go. Both implementations apply modulo reduction after every addition, ensuring correctness for all allowed input sizes.