Valid Permutations for DI Sequence solution and explanation
3 more videos on this problem
【每日一题】903. Valid Permutations for DI Sequence, 5/21/2021Huifeng Guan · 24:42 · 1K views
903. Valid Permutations for DI Sequence (Leetcode Hard)Programming Live with Larry · 37:06 · 1K views
LeetCode 903: Valid Permutations for DI SequenceAlitaCode · 31:01 · 101 views
No Sound Leetcode 903: Valid Permutations for DI SequenceExtremeProgrammer · 3:40 · 56 views
The problem
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'.
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.
def numPermsDISequence(s: str) -> int:
n = len(s)
MOD = 10**9 + 7
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(i + 1):
if s[i - 1] == 'I':
dp[i][j] = sum(dp[i - 1][k] for k in range(j)) % MOD
else:
dp[i][j] = sum(dp[i - 1][k] for k in range(j, i)) % MOD
return sum(dp[n]) % MOD
print(numPermsDISequence("DID"))import java.util.Arrays;
class Solution {
public int numPermsDISequence(String s) {
int n = s.length();
int MOD = 1000000007;
int[][] dp = new int[n + 1][n + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i; j++) {
if (s.charAt(i - 1) == 'I') {
for (int k = 0; k < j; k++) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
}
} else {
for (int k = j; k < i; k++) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
}
}
}
}
int result = 0;
for (int j = 0; j <= n; j++) {
result = (result + dp[n][j]) % MOD;
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.numPermsDISequence("DID"));
}
}#include <iostream>
#include <vector>
class Solution {
public:
int numPermsDISequence(std::string s) {
int n = s.size();
int MOD = 1e9 + 7;
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= i; ++j) {
if (s[i - 1] == 'I') {
for (int k = 0; k < j; ++k) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
}
} else {
for (int k = j; k < i; ++k) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
}
}
}
}
int result = 0;
for (int j = 0; j <= n; ++j) {
result = (result + dp[n][j]) % MOD;
}
return result;
}
};
int main() {
Solution sol;
std::cout << sol.numPermsDISequence("DID") << std::endl;
return 0;
}function numPermsDISequence(s) {
const n = s.length;
const MOD = 1000000007;
const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
dp[0][0] = 1;
for (let i = 1; i <= n; i++) {
for (let j = 0; j <= i; j++) {
if (s[i - 1] === 'I') {
for (let k = 0; k < j; k++) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
}
} else {
for (let k = j; k < i; k++) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
}
}
}
}
return dp[n].reduce((acc, curr) => (acc + curr) % MOD, 0);
}
console.log(numPermsDISequence("DID"));#include <stdio.h>
#define MOD 1000000007
int numPermsDISequence(char *s) {
int n = strlen(s);
int dp[n + 1][n + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= i; ++j) {
if (s[i - 1] == 'I') {
for (int k = 0; k < j; ++k) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
}
} else {
for (int k = j; k < i; ++k) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
}
}
}
}
int result = 0;
for (int j = 0; j <= n; ++j) {
result = (result + dp[n][j]) % MOD;
}
return result;
}
int main() {
printf("%d\n", numPermsDISequence("DID"));
return 0;
}using System;
public class Solution {
public int NumPermsDISequence(string s) {
int n = s.Length;
int MOD = 1000000007;
int[,] dp = new int[n + 1, n + 1];
dp[0, 0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i; j++) {
if (s[i - 1] == 'I') {
for (int k = 0; k < j; k++) {
dp[i, j] = (dp[i, j] + dp[i - 1, k]) % MOD;
}
} else {
for (int k = j; k < i; k++) {
dp[i, j] = (dp[i, j] + dp[i - 1, k]) % MOD;
}
}
}
}
int result = 0;
for (int j = 0; j <= n; j++) {
result = (result + dp[n, j]) % MOD;
}
return result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.NumPermsDISequence("DID"));
}
}This Python solution uses list comprehension within the loops to update the dp entry. The code computes the cumulative number of valid permutations aligning with the DI sequence constraints. The nested loops populate the DP table, and the final result aggregates the 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.
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.
def numPermsDISequence(s: str) -> int:
n = len(s)
MOD = 10**9 + 7
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
suffix_sum = [0] * (i + 1)
for k in range(i):
suffix_sum[k + 1] = (suffix_sum[k] + dp[i - 1][k]) % MOD
for j in range(i + 1):
if s[i - 1] == 'I':
dp[i][j] = suffix_sum[j]
else:
dp[i][j] = (suffix_sum[i] - suffix_sum[j] + MOD) % MOD
return sum(dp[n]) % MOD
print(numPermsDISequence("DID"))#include <iostream>
#include <vector>
class Solution {
public:
int numPermsDISequence(std::string s) {
int n = s.size();
int MOD = 1e9 + 7;
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
std::vector<int> suffixSum(i + 1, 0);
for (int j = 0; j < i; ++j) {
suffixSum[j + 1] = (suffixSum[j] + dp[i - 1][j]) % MOD;
}
for (int j = 0; j <= i; ++j) {
if (s[i - 1] == 'I') {
dp[i][j] = suffixSum[j];
} else {
dp[i][j] = (suffixSum[i] - suffixSum[j] + MOD) % MOD;
}
}
}
int result = 0;
for (int j = 0; j <= n; ++j) {
result = (result + dp[n][j]) % MOD;
}
return result;
}
};
int main() {
Solution sol;
std::cout << sol.numPermsDISequence("DID") << std::endl;
return 0;
}This Python solution achieves more efficient computation using a suffix sum array. The suffix sum allows for the quick computation of range sums by maintaining a running total of sums, optimizing the transition between states in the DP table.
Time Complexity: O(n^2), where n is the length of the input string.
Space Complexity: O(n^2) due to the DP table and suffix sums.
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.
function numPermsDISequence(s: string): number {
const n = s.length;
const f: number[][] = Array(n + 1)
.fill(0)
.map(() => Array(n + 1).fill(0));
f[0][0] = 1;
const mod = 10 ** 9 + 7;
for (let i = 1; i <= n; ++i) {
if (s[i - 1] === 'D') {
for (let j = 0; j <= i; ++j) {
for (let k = j; k < i; ++k) {
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
}
}
} else {
for (let j = 0; j <= i; ++j) {
for (let k = 0; k < j; ++k) {
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
}
}
}
}
let ans = 0;
for (let j = 0; j <= n; ++j) {
ans = (ans + f[n][j]) % mod;
}
return ans;
}func numPermsDISequence(s string) (ans int) {
const mod = 1e9 + 7
n := len(s)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, n+1)
}
f[0][0] = 1
for i := 1; i <= n; i++ {
if s[i-1] == 'D' {
for j := 0; j <= i; j++ {
for k := j; k < i; k++ {
f[i][j] = (f[i][j] + f[i-1][k]) % mod
}
}
} else {
for j := 0; j <= i; j++ {
for k := 0; k < j; k++ {
f[i][j] = (f[i][j] + f[i-1][k]) % mod
}
}
}
}
for j := 0; j <= n; j++ {
ans = (ans + f[n][j]) % mod
}
return
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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!).