Skip to main content
Talentd

Valid Permutations for DI Sequence - Solution & Explanation

HardStringDynamic ProgrammingPrefix Sum19 min read
Practice this problem

Problem Statement

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'.

Approach Overview

Problem Overview: You are given a string s consisting of characters 'D' (decreasing) and 'I' (increasing). Construct a permutation of numbers [0..n] such that each adjacent pair follows the pattern in s. The goal is to count how many valid permutations satisfy the entire sequence.

Approach 1: Brute Force Permutation Check (O(n! * n) time, O(n) space)

Generate every permutation of numbers 0..n and verify whether the ordering satisfies the DI pattern. For each permutation, iterate through the string and check whether perm[i] < perm[i+1] when the character is 'I' or perm[i] > perm[i+1] when it is 'D'. This guarantees correctness but quickly becomes infeasible since the number of permutations grows factorially. It is useful only for understanding the constraint behavior on very small inputs.

Approach 2: Dynamic Programming (O(n^3) time, O(n^2) space)

Instead of generating permutations, track how many valid sequences can be formed using dynamic programming. Let dp[i][j] represent the number of valid ways to build the first i characters of the pattern where the i-th number is the j-th smallest among the remaining numbers. For each position, you iterate over possible previous ranks depending on whether the current character is 'I' or 'D'. For 'I', sum all states with smaller rank; for 'D', sum states with larger rank. Directly summing ranges inside loops results in cubic time.

Approach 3: Optimized DP with Prefix/Suffix Sums (O(n^2) time, O(n^2) space)

The key optimization removes repeated summation in the DP transition. Instead of recomputing sums of ranges every time, maintain prefix or suffix cumulative sums of the previous DP row. When the character is 'I', use a prefix sum to quickly compute the total of all smaller ranks. When it is 'D', use a suffix sum to accumulate counts from larger ranks. Each DP row can then be filled in linear time, reducing the overall complexity to quadratic. This approach scales comfortably within problem constraints and is the typical competitive programming solution.

The technique relies heavily on dynamic programming state design and range-sum acceleration using prefix sum arrays. The input constraint is represented as a string, but the core challenge lies in counting valid orderings efficiently.

Recommended for interviews: Interviewers expect the optimized dynamic programming solution with prefix or suffix sums. Starting with the basic DP formulation shows you understand the ranking-based state transition. Applying prefix sums to reduce the nested summation from O(n) per state to O(1) demonstrates strong optimization skills and familiarity with common DP acceleration techniques.

Approach 1: Dynamic Programming Approach

The dynamic programming approach involves building a DP table where dp[i][j] represents the number of valid permutations of [0, i] using the first j characters of the string s.

We initialize dp[0][0] = 1 because there is exactly one way to arrange a single element.

We fill the table by iterating over all possible lengths and considering the conditions dictated by 'I' and 'D'. For 'I', count all valid j placements for the current i. For 'D', count in reverse fashion.

This C solution initializes a DP table with dimensions (n+1) x (n+1). It fills up this DP table based on the condition of 'I' and 'D', using all allowable sequences at each step to build up to the full string length. Finally, it calculates the result by summing up all possible valid permutations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3), where n is the length of the string.
Space Complexity: O(n^2) due to the DP table.

Try this approach in the editor β†’

Approach 2: Optimized Dynamic Programming with Suffix Sum Array

This approach optimizes the previous dynamic programming solution using a suffix sum array to reduce the time complexity.

It involves calculating the suffix sum of the previous row in the DP table to allow O(1) transitions instead of recalculating the range sum for each state.

This C++ code improves the basic dynamic programming method by leveraging the suffix sum optimization. Rather than recalculating sums for every possible permutation condition on 'I' or 'D', it uses a precomputed sum of elements up to a given point, thereby reducing unnecessary calculations and improving time efficiency.

Code

C++Python

C++

Python

Complexity

Time Complexity: O(n^2), where n is the length of the input string.
Space Complexity: O(n^2) due to the 2D DP table and suffix sums.

Try this approach in the editor β†’

Approach 3: Dynamic Programming

We define f[i][j] as the number of permutations that satisfy the problem's requirements with the first i characters of the string ending with the number j. Initially, f[0][0]=1, and the rest f[0][j]=0. The answer is sum_{j=0}^n f[n][j].

Consider f[i][j], where j \in [0, i].

If the ith character s[i-1] is 'D', then f[i][j] can be transferred from f[i-1][k], where k \in [j+1, i]. Since k-1 can only be up to i-1, we move k one place to the left, so k \in [j, i-1]. Therefore, we have f[i][j] = sum_{k=j}^{i-1} f[i-1][k].

If the ith character s[i-1] is 'I', then f[i][j] can be transferred from f[i-1][k], where k \in [0, j-1]. Therefore, we have f[i][j] = sum_{k=0}^{j-1} f[i-1][k].

The final answer is sum_{j=0}^n f[n][j].

The time complexity is O(n^3), and the space complexity is O(n^2). Here, n is the length of the string.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n^3), where n is the length of the string.
Space Complexity: O(n^2) due to the DP table.

Optimized Dynamic Programming with Suffix Sum Array

Time Complexity: O(n^2), where n is the length of the input string.
Space Complexity: O(n^2) due to the 2D DP table and suffix sums.

Dynamic Programmingβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Permutation GenerationO(n! * n)O(n)Only for understanding the problem or testing with very small inputs
Dynamic Programming with Range SummationO(n^3)O(n^2)Useful for deriving the recurrence and understanding rank-based transitions
Optimized DP with Prefix/Suffix SumsO(n^2)O(n^2)Preferred solution for interviews and competitive programming

Video Solution

【每ζ—₯δΈ€ι’˜γ€‘903. Valid Permutations for DI Sequence, 5/21/2021 β€’ Huifeng Guan β€’ 1,409 views views

Watch 3 more video solutions β†’

Frequently Asked Questions

Is Valid Permutations for DI Sequence easy or hard?
Valid Permutations for DI Sequence is classified as a Hard problem because it requires careful DP state design and optimization with prefix or suffix sums. The core challenge is counting valid permutations without explicitly generating them.
Valid Permutations for DI Sequence Python/Java solution
Implement the DP table where each row corresponds to the processed prefix of the DI string. Use prefix sums for 'I' cases and suffix sums for 'D' cases to fill the next row efficiently. The same algorithm works across Python, Java, C++, C#, and JavaScript implementations.
How to solve Valid Permutations for DI Sequence in O(n^2)?
Use dynamic programming where dp[i][j] represents the number of valid permutations for the first i characters ending with the j-th smallest unused value. Instead of summing ranges repeatedly, maintain prefix sums for 'I' transitions and suffix sums for 'D' transitions. This reduces each DP row computation to linear time.
What is the best approach for Valid Permutations for DI Sequence?
The most efficient approach uses dynamic programming combined with prefix or suffix sums. The DP state tracks how many ways a permutation prefix can end with a certain relative rank. Prefix or suffix cumulative sums allow range transitions to be computed in O(1), giving an overall time complexity of O(n^2).
Is Valid Permutations for DI Sequence asked at Google/Amazon/Meta?
Dynamic programming counting problems with ordering constraints appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving permutations, inequalities, and DP with prefix sums are common in advanced algorithm interviews.
What data structure is used in Valid Permutations for DI Sequence?
The solution primarily uses a 2D dynamic programming array to store counts of valid states. Prefix or suffix sum arrays are used to accelerate range sum calculations during DP transitions.
What is the time complexity of Valid Permutations for DI Sequence?
The optimized solution runs in O(n^2) time with O(n^2) space using dynamic programming and prefix or suffix sum optimization. A straightforward DP without range optimization can degrade to O(n^3), while brute force permutation generation is O(n!).

Ready to solve this problem?

Practice Valid Permutations for DI Sequence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring