Problem Description

You are given a string s of length n consisting of characters 'D' and 'I':

• 'D' means the next number should be decreasing
• 'I' means the next number should be increasing

You need to find how many valid permutations exist for n + 1 integers from the range [0, n].

A permutation perm is considered valid if:

• When s[i] == 'D', then perm[i] > perm[i + 1] (decreasing)
• When s[i] == 'I', then perm[i] < perm[i + 1] (increasing)

For example, if s = "DID":

• The permutation has 4 numbers (from 0 to 3)
• Position 0 to 1 should be decreasing (D)
• Position 1 to 2 should be increasing (I)
• Position 2 to 3 should be decreasing (D)
• A valid permutation could be [2, 0, 3, 1] because 2 > 0 (D), 0 < 3 (I), and 3 > 1 (D)

The task is to count the total number of valid permutations. Since this number can be very large, return the result modulo 10^9 + 7.

The dynamic programming solution uses f[i][j] to represent the number of valid permutations for the first i characters where the element at position i has rank j among all elements up to position i. The transitions depend on whether the current character is 'D' or 'I':

• For 'D': The current element must be greater than the next, so we sum contributions from higher-ranked previous positions
• For 'I': The current element must be less than the next, so we sum contributions from lower-ranked previous positions

Intuition

The key insight is to think about relative rankings rather than absolute values. When we place numbers in a permutation, what matters is not the specific values but their relative order.

Consider building the permutation step by step. At each position, we need to decide which "rank" the current number should have among all numbers placed so far. For example, if we've placed 3 numbers, the new number could be the smallest (rank 0), second smallest (rank 1), third smallest (rank 2), or largest (rank 3) among these 4 numbers.

Why does this ranking approach work? When we insert a new number into an existing valid sequence:

• If we need a decrease ('D'), the new number must be smaller than the previous one
• If we need an increase ('I'), the new number must be larger than the previous one

The brilliant observation is that when we insert a new number with rank j, all existing numbers with rank ≥ j get their ranks shifted up by 1. This shift preserves the relative ordering between existing numbers while establishing the correct relationship with the new number.

For a 'D' transition: If the previous number had rank k and we insert a new number with rank j where j < k, then after insertion, the previous number's rank becomes k+1. Since k+1 > j, we maintain the decreasing property. This works when j ≤ k.

For an 'I' transition: If the previous number had rank k and we insert a new number with rank j where j > k, then the previous number keeps rank k. Since k < j, we maintain the increasing property. This works when j > k.

This leads us to define f[i][j] as the number of ways to arrange the first i+1 numbers where the number at position i has rank j among these i+1 numbers. The transitions naturally follow:

• For 'D': Sum all f[i-1][k] where k ≥ j (which becomes k ∈ [j, i-1] after adjustment)
• For 'I': Sum all f[i-1][k] where k < j (which is k ∈ [0, j-1])

Learn more about Dynamic Programming and Prefix Sum patterns.

Solution Approach

We implement the dynamic programming solution using a 2D array f[i][j] where:

• i represents we've processed the first i characters of string s
• j represents the rank of the element at position i among all i+1 elements

Initialization:

• Create a 2D array f of size (n+1) × (n+1) initialized with zeros
• Set f[0][0] = 1 as the base case (one element with rank 0)

State Transitions:

For each character s[i-1] at position i (1-indexed):

1. When s[i-1] == 'D' (Decreasing):

   • For each possible rank j of the current position (from 0 to i)
   • Sum contributions from previous states where rank k ∈ [j, i-1]
   • Formula: f[i][j] = Σ(f[i-1][k]) for k from j to i-1
   • This ensures the previous element (after rank adjustment) will be greater

2. When s[i-1] == 'I' (Increasing):

   • For each possible rank j of the current position (from 0 to i)
   • Sum contributions from previous states where rank k ∈ [0, j-1]
   • Formula: f[i][j] = Σ(f[i-1][k]) for k from 0 to j-1
   • This ensures the previous element keeps a smaller rank

Implementation Details:

for i, c in enumerate(s, 1):  # Process each character, i starts from 1
    if c == "D":
        for j in range(i + 1):  # j can be from 0 to i
            for k in range(j, i):  # Sum from j to i-1
                f[i][j] = (f[i][j] + f[i-1][k]) % mod
    else:  # c == "I"
        for j in range(i + 1):  # j can be from 0 to i
            for k in range(j):  # Sum from 0 to j-1
                f[i][j] = (f[i][j] + f[i-1][k]) % mod

Final Answer:

• Sum all possible ranks at the final position: Σ(f[n][j]) for j from 0 to n
• Apply modulo 10^9 + 7 to handle large numbers

Time Complexity: O(n³) due to three nested loops Space Complexity: O(n²) for the 2D DP array

Example Walkthrough

Let's walk through the solution with s = "DI":

We need to find valid permutations of [0, 1, 2] (3 numbers for string length 2).

Step 1: Initialize DP table

• Create f[3][3] array (since we have n=2, we need n+1=3 rows)
• Set f[0][0] = 1 (base case: one number at rank 0)

Initial state:

f[0] = [1, 0, 0]
f[1] = [0, 0, 0]
f[2] = [0, 0, 0]

Step 2: Process first character 'D' (i=1)

For 'D', we need decreasing transition. For each rank j at position 1:

• j=0: Sum f[0][k] for k ∈ [0, 0] → f[1][0] = f[0][0] = 1
• j=1: Sum f[0][k] for k ∈ [1, 0] → No valid k, so f[1][1] = 0

After processing 'D':

f[0] = [1, 0, 0]
f[1] = [1, 0, 0]
f[2] = [0, 0, 0]

This means after placing 2 numbers with 'D' constraint, we have 1 way where the second number has rank 0 (is the smaller of the two).

Step 3: Process second character 'I' (i=2)

For 'I', we need increasing transition. For each rank j at position 2:

• j=0: Sum f[1][k] for k ∈ [0, -1] → No valid k, so f[2][0] = 0
• j=1: Sum f[1][k] for k ∈ [0, 0] → f[2][1] = f[1][0] = 1
• j=2: Sum f[1][k] for k ∈ [0, 1] → f[2][2] = f[1][0] + f[1][1] = 1 + 0 = 1

Final state:

f[0] = [1, 0, 0]
f[1] = [1, 0, 0]
f[2] = [0, 1, 1]

Step 4: Calculate final answer Sum all values in the last row: f[2][0] + f[2][1] + f[2][2] = 0 + 1 + 1 = 2

Verification: The 2 valid permutations for "DI" are:

1. [2, 0, 1]: 2 > 0 (D), 0 < 1 (I) ✓
2. [1, 0, 2]: 1 > 0 (D), 0 < 2 (I) ✓

Our DP solution correctly found 2 valid permutations!

Understanding the rank interpretation:

• When f[2][1] = 1: This represents permutations where the last element has rank 1 (middle value) among all 3 elements
• When f[2][2] = 1: This represents permutations where the last element has rank 2 (largest value) among all 3 elements
• Both contribute to valid permutations satisfying the "DI" pattern

Solution Implementation

Time and Space Complexity

The time complexity is O(n³), where n is the length of the string s.

This is because:

• The outer loop iterates through each character in string s, running n times
• For each iteration, we have nested loops with indices j and k
• The j loop runs from 0 to i, which can be at most n+1 iterations
• The inner k loop runs either from j to i (for "D") or from 0 to j-1 (for "I"), contributing at most O(n) iterations
• Overall: O(n) × O(n) × O(n) = O(n³)

The space complexity is O(n²).

This is because:

• We create a 2D array f with dimensions (n+1) × (n+1)
• This requires O((n+1)²) = O(n²) space
• The additional variables use only O(1) space
• Therefore, the total space complexity is O(n²)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusion About Rank Interpretation

The most common pitfall is misunderstanding what "rank" means in the DP state. Many developers incorrectly interpret dp[i][j] as the actual value at position i rather than its relative rank among the first i+1 elements.

Wrong Understanding:

• Thinking j represents the actual number (0, 1, 2, ..., n) at position i
• This leads to incorrect state transitions since the actual values don't directly determine the validity

Correct Understanding:

• j represents the rank (0-indexed) of the element at position i when considering only the first i+1 positions
• Rank 0 means smallest among those i+1 elements, rank i means largest

2. Incorrect Range Boundaries in Transitions

Another critical error is using wrong loop boundaries when accumulating from previous states.

Common Mistakes:

# WRONG: Off-by-one errors
if char == "D":
    for k in range(j + 1, i + 1):  # Should be range(j, i)
        dp[i][j] += dp[i-1][k]

# WRONG: Including invalid indices
if char == "I":
    for k in range(0, j):  # This is correct, but often written as range(0, j+1)
        dp[i][j] += dp[i-1][k]

Solution: Always remember:

• For 'D': Sum from k = j to k = i-1 (inclusive)
• For 'I': Sum from k = 0 to k = j-1 (inclusive)

3. Forgetting Modulo Operations

Since the result can be very large, forgetting to apply modulo at each step can cause integer overflow in languages with fixed integer sizes, or incorrect results due to precision issues.

Wrong:

dp[i][j] = dp[i][j] + dp[i-1][k]  # Missing modulo

Correct:

dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD

4. Space Optimization Pitfall

When attempting to optimize space from O(n²) to O(n) using rolling arrays, a common mistake is updating values in-place without preserving the previous row's values properly.

Wrong Space Optimization:

# Using single array incorrectly
dp = [0] * (n + 2)
dp[0] = 1
for i, char in enumerate(s, 1):
    for j in range(i + 1):
        # This modifies dp while still reading from it!
        if char == "D":
            dp[j] = sum(dp[k] for k in range(j, i)) % MOD

Correct Space Optimization:

# Use two arrays and swap
prev = [0] * (n + 2)
curr = [0] * (n + 2)
prev[0] = 1

for i, char in enumerate(s, 1):
    curr = [0] * (n + 2)  # Reset current row
    if char == "D":
        for j in range(i + 1):
            for k in range(j, i):
                curr[j] = (curr[j] + prev[k]) % MOD
    else:
        for j in range(i + 1):
            for k in range(j):
                curr[j] = (curr[j] + prev[k]) % MOD
    prev, curr = curr, prev  # Swap for next iteration

result = sum(prev[j] for j in range(n + 1)) % MOD

5. Index Confusion Between String and DP Array

The string s has length n, but we're creating permutations of n+1 elements. This off-by-one relationship often causes indexing errors.

Key Points to Remember:

• String s has indices from 0 to n-1
• DP array dp[i] represents states after processing i characters (so i goes from 0 to n)
• When at dp[i], we look at s[i-1] to determine the transition
• The final answer sums dp[n][j] for all valid j