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:
s[i] == 'D', then perm[i] > perm[i + 1], ands[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.length1 <= n <= 200s[i] is either 'I' or 'D'.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.
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.
Time Complexity: O(n^3), where n is the length of the string.
Space Complexity: O(n^2) due to the DP table.
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.
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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^3), where n is the length of the string. |
| Optimized Dynamic Programming with Suffix Sum Array | Time Complexity: O(n^2), where n is the length of the input string. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutation Generation | O(n! * n) | O(n) | Only for understanding the problem or testing with very small inputs |
| Dynamic Programming with Range Summation | O(n^3) | O(n^2) | Useful for deriving the recurrence and understanding rank-based transitions |
| Optimized DP with Prefix/Suffix Sums | O(n^2) | O(n^2) | Preferred solution for interviews and competitive programming |
【每日一题】903. Valid Permutations for DI Sequence, 5/21/2021 • Huifeng Guan • 1,406 views views
Watch 5 more video solutions →Practice Valid Permutations for DI Sequence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor