Watch 6 video solutions for Valid Permutations for DI Sequence, a hard level problem involving String, Dynamic Programming, Prefix Sum. This walkthrough by Huifeng Guan has 1,406 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |