Given a string S consisting only of the characters 'D' (for "decrease") and 'I' (for "increase"), you are to return the number of valid permutations of the integers 0 to n (where n = len(S)) such that for each character S[i]:
S[i] == 'I', then the i-th element of the permutation is less than the (i+1)-th element.S[i] == 'D', then the i-th element of the permutation is greater than the (i+1)-th element.
Each permutation must use every number from 0 to n exactly once. Return the total number of valid permutations modulo 10^9 + 7.
Constraints:
1 <= S.length <= 200S is either 'I' or 'D'
At first glance, this problem looks like a permutation generation task with constraints, which might suggest generating all possible permutations and filtering them. However, with n up to 200, this approach is computationally impossible, as the number of permutations grows factorially.
Instead, we can think recursively: for each position, we want to know how many ways we can fill it, given the previous choices and the current 'I' or 'D' requirement. This leads us to dynamic programming, where we keep track of the number of valid ways to fill the first i positions ending with a certain number.
By building up solutions for smaller subproblems and reusing them, we can avoid redundant work and solve the problem efficiently.
We use dynamic programming (DP) to efficiently count the number of valid permutations. Here's how:
dp[i][j] represent the number of ways to arrange the first i numbers, ending with the j-th smallest unused number.i = 0), there is only one way to pick the first number, so dp[0][j] = 1 for all j in 0...n.i and for each possible j (which represents the count of smaller numbers left), update dp[i][j] based on whether S[i-1] is 'I' or 'D'.S[i-1] == 'I', then the current number must be greater than the previous one, so sum up dp[i-1][k] for k = 0 to j-1.
S[i-1] == 'D', then the current number must be less, so sum up dp[i-1][k] for k = j to i-1.
dp[n][j] for j from 0 to n.
Let's take S = "DID" as an example. Here, n = 3, so we use numbers from 0 to 3.
dp[0][j] = 1 for j = 0,1,2,3.j, dp[1][j] = sum(dp[0][k]) for k = j to 0 (since we want a decrease).dp[1][0] = dp[0][0]+dp[0][1]+dp[0][2]+dp[0][3]=4, dp[1][1]=3, dp[1][2]=2, dp[1][3]=1.j, dp[2][j] = sum(dp[1][k]) for k = 0 to j-1 (since we want an increase).dp[2][j] using the prefix sum of previous row.dp[3][j] to get the answer.
In this example, the answer is 5.
MOD = 10 ** 9 + 7
class Solution:
def numPermsDISequence(self, S: str) -> int:
n = len(S)
dp = [1] * (n + 1)
for i in range(1, n + 1):
new = [0] * (n + 1)
if S[i - 1] == 'I':
curr = 0
for j in range(i):
curr = (curr + dp[j]) % MOD
new[j] = curr
else: # 'D'
curr = 0
for j in range(i - 1, -1, -1):
curr = (curr + dp[j + 1]) % MOD
new[j] = curr
dp = new
return sum(dp) % MOD
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int numPermsDISequence(string S) {
const int MOD = 1e9 + 7;
int n = S.size();
vector<int> dp(n + 1, 1);
for (int i = 1; i <= n; ++i) {
vector<int> new_dp(n + 1, 0);
if (S[i - 1] == 'I') {
int curr = 0;
for (int j = 0; j < i; ++j) {
curr = (curr + dp[j]) % MOD;
new_dp[j] = curr;
}
} else {
int curr = 0;
for (int j = i - 1; j >= 0; --j) {
curr = (curr + dp[j + 1]) % MOD;
new_dp[j] = curr;
}
}
dp = new_dp;
}
int ans = 0;
for (int x : dp) ans = (ans + x) % MOD;
return ans;
}
};
class Solution {
public int numPermsDISequence(String S) {
int MOD = 1000000007;
int n = S.length();
int[] dp = new int[n + 1];
for (int i = 0; i <= n; ++i) dp[i] = 1;
for (int i = 1; i <= n; ++i) {
int[] newDp = new int[n + 1];
if (S.charAt(i - 1) == 'I') {
int curr = 0;
for (int j = 0; j < i; ++j) {
curr = (curr + dp[j]) % MOD;
newDp[j] = curr;
}
} else {
int curr = 0;
for (int j = i - 1; j >= 0; --j) {
curr = (curr + dp[j + 1]) % MOD;
newDp[j] = curr;
}
}
dp = newDp;
}
int ans = 0;
for (int x : dp) ans = (ans + x) % MOD;
return ans;
}
}
var numPermsDISequence = function(S) {
const MOD = 1e9 + 7;
const n = S.length;
let dp = new Array(n + 1).fill(1);
for (let i = 1; i <= n; ++i) {
let newDp = new Array(n + 1).fill(0);
if (S[i - 1] === 'I') {
let curr = 0;
for (let j = 0; j < i; ++j) {
curr = (curr + dp[j]) % MOD;
newDp[j] = curr;
}
} else {
let curr = 0;
for (let j = i - 1; j >= 0; --j) {
curr = (curr + dp[j + 1]) % MOD;
newDp[j] = curr;
}
}
dp = newDp;
}
return dp.reduce((a, b) => (a + b) % MOD, 0);
};
(n+1)! permutations, checking each for validity, which is infeasible for large n.O((n+1)!), Space Complexity: O(n) for recursion stack.(n+1) x (n+1), but with rolling arrays, we use only O(n) space.i involves O(i) work, so total time is O(n^2).O(n) (with rolling DP rows).The key insight for solving the "Valid Permutations for DI Sequence" problem is to model the constraints using dynamic programming, breaking the problem into subproblems based on the current state and previous choices. By using prefix sums and a compact DP structure, we efficiently count the number of valid permutations without generating them all. This approach is both elegant and practical, scaling easily to the problem's constraints.