Valid Permutations for DI Sequence
HardPrompt
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', thenperm[i] > perm[i + 1], and - If
s[i] == 'I', thenperm[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'.
Approaches
3 approaches with complexity analysis and trade-offs.
A naive approach is to generate every possible permutation of numbers from 0 to n, and then check if each permutation satisfies the conditions given by the string s. This is highly inefficient. A better, but still too slow, approach is to use backtracking. We can build a permutation one number at a time, and if at any step the condition is violated, we stop exploring that path (pruning).
Algorithm
- Create a recursive function, say
countValidPermutations(currentPermutation, usedNumbers). - The base case: if the
currentPermutationhas lengthn + 1, we have found one valid permutation, so return 1. - In the recursive step, iterate through all numbers
numfrom0ton. - If
numhas not been used yet:- Add
numto thecurrentPermutation. - Before recursing, check if the new partial permutation is valid. If
currentPermutationhas at least two elements, checkcurrentPermutation[k-1]andcurrentPermutation[k]againsts[k-1]. - If it's valid, call the function recursively and add the result to a running total.
- Backtrack: remove
numfrom the permutation and mark it as unused to explore other possibilities.
- Add
- The total count is the sum of results from all valid recursive calls.
Walkthrough
We define a recursive function that tries to place an unused number at the next position in the permutation. The function keeps track of the permutation being built and which numbers from [0, n] have already been used. At each step, we try to append an unused number. If the new number maintains the validity of the permutation according to the DI sequence, we proceed recursively. If not, we prune this path and try another number. When a full permutation of length n+1 is formed, we count it as one valid permutation.
Complexity
Time
O((n+1)!) because in the worst case, it explores all possible permutations of `n+1` numbers.
Space
O(n) for the recursion stack depth and to keep track of used numbers.
Trade-offs
Pros
Conceptually simple to understand.
Correct for very small inputs.
Cons
Extremely high time complexity, making it infeasible for the given constraints.
Will result in a 'Time Limit Exceeded' error on most platforms.
Since the backtracking approach is too slow, we can look for overlapping subproblems and optimal substructure, which suggests dynamic programming. We can define a DP state based on the length of the permutation being built and the value of the last element.
Algorithm
- Create a 2D array
dp[n+1][n+1]. - Base case: For a length 1 permutation of
{0}, there's only one possibility:(0). So,dp[0][0] = 1. - Iterate
ifrom 1 ton(fors[0...i-1]).- Iterate
jfrom 0 toi(the last element of the new permutation).- If
s[i-1] == 'I', we needperm[i-1] < perm[i]. This means the last element of the previous permutation (after re-labeling) must be smaller thanj. This is possible if the original last elementkwas less thanj. So,dp[i][j] = sum(dp[i-1][k] for k from 0 to j-1). - If
s[i-1] == 'D', we needperm[i-1] > perm[i]. This means the last element of the previous permutation (after re-labeling) must be larger thanj. This is possible if the original last elementkwas greater than or equal toj. So,dp[i][j] = sum(dp[i-1][k] for k from j to i-1).
- If
- Iterate
- The final answer is the sum of all values in the last row
dp[n].
Walkthrough
Let dp[i][j] be the number of valid permutations for the prefix s[0...i-1] (of length i) using the numbers {0, 1, ..., i} where the last element of the permutation is j. The key insight is that the absolute values of numbers don't matter as much as their relative order. When we transition from a permutation of {0,...,i-1} to one of {0,...,i}, we are essentially inserting a new number and re-labeling the existing ones to maintain their relative order. This leads to a recurrence relation where dp[i][j] is calculated by summing up certain values from the dp[i-1] row. The specific range of the sum depends on whether s[i-1] is 'I' or 'D'.
Complexity
Time
O(N³) due to three nested loops (i, j, and k for the sum).
Space
O(N²) for the DP table.
Trade-offs
Pros
Significantly more efficient than backtracking.
Solves the problem for moderate values of n.
Cons
The O(N³) complexity might be too slow if n was larger.
Uses O(N²) space which can be improved.
The O(N³) DP approach can be optimized. The calculation for each dp[i][j] involves summing up a range of values from the previous row dp[i-1]. These are essentially prefix sums or suffix sums. We can compute these sums more efficiently.
Algorithm
- Initialize a 1D
dparraydp = [1], representing the base case for a permutation of length 1. - Loop
ifrom 1 ton. In each iteration,dpholds the values for permutations of lengthi, and we computenewDpfor permutations of lengthi+1.- Create a
newDparray of sizei+1. - If
s[i-1] == 'I':- Initialize
currentSum = 0. - Iterate
jfrom 0 toi. SetnewDp[j] = currentSum, then updatecurrentSumby addingdp[j](from the previous iteration's array).
- Initialize
- If
s[i-1] == 'D':- Initialize
currentSum = 0. - Iterate
jfromidown to 0. SetnewDp[j] = currentSum, then updatecurrentSumby addingdp[j-1].
- Initialize
- Replace
dpwithnewDpfor the next iteration.
- Create a
- After the loop, sum all elements in the final
dparray to get the total count.
Walkthrough
Instead of re-calculating the sum in an inner loop every time, we can calculate the new DP row dp[i] based on dp[i-1] in a single pass.
- If
s[i-1] == 'I',dp[i][j]is the prefix sumdp[i-1][0] + ... + dp[i-1][j-1]. We can compute this for alljby maintaining a running sum as we iterate throughj. - If
s[i-1] == 'D',dp[i][j]is the suffix sumdp[i-1][j] + ... + dp[i-1][i-1]. We can compute this for alljby iterating backwards and maintaining a running sum. This optimization reduces the time complexity toO(N²). Furthermore, sincedp[i]only depends ondp[i-1], we can optimize space toO(N)by only storing the current and previous DP rows.
class Solution { public int numPermsDISequence(String s) { int n = s.length(); int MOD = 1_000_000_007; // dp[j] represents the number of valid permutations for the prefix of s of length i-1, // using numbers {0, ..., i-1}, ending with j. int[] dp = new int[1]; dp[0] = 1; // Base case: i=0, s="", perm of {0} is (0). for (int i = 1; i <= n; i++) { int[] newDp = new int[i + 1]; if (s.charAt(i - 1) == 'I') { int currentSum = 0; for (int j = 0; j <= i; j++) { newDp[j] = currentSum; if (j < i) { // dp is from prev iteration, has i elements (0 to i-1) currentSum = (currentSum + dp[j]) % MOD; } } } else { // s.charAt(i - 1) == 'D' int currentSum = 0; for (int j = i; j >= 0; j--) { newDp[j] = currentSum; if (j > 0) { // dp has i elements, need to access dp[j-1] currentSum = (currentSum + dp[j - 1]) % MOD; } } } dp = newDp; } long total = 0; for (int count : dp) { total = (total + count) % MOD; } return (int) total; }}Complexity
Time
O(N²) due to the two nested loops. The outer loop runs `n` times, and the inner loop runs `i+1` times, where `i` goes up to `n`.
Space
O(N) with space optimization, as we only need to store the DP values for the previous length to compute the current one. Without this optimization, it would be O(N²).
Trade-offs
Pros
Optimal time complexity that passes the given constraints.
Space can be optimized to O(N).
Cons
The DP state and transitions are clever and might not be immediately obvious.
Solutions
Solution
class Solution {public int numPermsDISequence(String s) { final int mod = (int)1 e9 + 7; int n = s.length(); int[] f = new int[n + 1]; f[0] = 1; for (int i = 1; i <= n; ++i) { int pre = 0; int[] g = new int[n + 1]; if (s.charAt(i - 1) == 'D') { for (int j = i; j >= 0; --j) { pre = (pre + f[j]) % mod; g[j] = pre; } } else { for (int j = 0; j <= i; ++j) { g[j] = pre; pre = (pre + f[j]) % mod; } } f = g; } int ans = 0; for (int j = 0; j <= n; ++j) { ans = (ans + f[j]) % mod; } return ans; }}class Solution {public: int numPermsDISequence(string s) { const int mod = 1e9 + 7; int n = s.size(); vector<int> f(n + 1); f[0] = 1; for (int i = 1; i <= n; ++i) { int pre = 0; vector<int> g(n + 1); if (s[i - 1] == 'D') { for (int j = i; j >= 0; --j) { pre = (pre + f[j]) % mod; g[j] = pre; } } else { for (int j = 0; j <= i; ++j) { g[j] = pre; pre = (pre + f[j]) % mod; } } f = move(g); } int ans = 0; for (int j = 0; j <= n; ++j) { ans = (ans + f[j]) % mod; } return ans; }};class Solution: def numPermsDISequence(self, s: str) -> int: mod = 10 ** 9 + 7 n = len(s) f = [1] + [0] * n for i, c in enumerate(s, 1): pre = 0 g = [0] * (n + 1) if c == "D": for j in range(i, - 1, - 1): pre = (pre + f[j]) % mod g[j] = pre else: for j in range(i + 1): g[j] = pre pre = (pre + f[j]) % mod f = g return sum(f) % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.