Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/903.html
903. Valid Permutations for DI Sequence (Hard)
We are given S
, a length n
string of characters from the set {'D', 'I'}
. (These letters stand for "decreasing" and "increasing".)
A valid permutation is a permutation P[0], P[1], ..., P[n]
of integers {0, 1, ..., n}
, such that for all i
:
- If
S[i] == 'D'
, thenP[i] > P[i+1]
, and; - If
S[i] == 'I'
, thenP[i] < P[i+1]
.
How many valid permutations are there? Since the answer may be large, return your answer modulo 10^9 + 7
.
Example 1:
Input: "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)
Note:
1 <= S.length <= 200
S
consists only of characters from the set{'D', 'I'}
.
Related Topics:
Divide and Conquer, Dynamic Programming
Solution 1. DP
// OJ: https://leetcode.com/problems/valid-permutations-for-di-sequence/
// Time: O(N^2)
// Space: O(N)
// Ref: https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/168278/C%2B%2BJavaPython-DP-Solution-O(N2)
class Solution {
public:
int numPermsDISequence(string S) {
int N = S.size(), mod = 1e9 + 7;
vector<int> dp(N + 1, 1), dp2(N);
for (int i = 0; i < N; dp = dp2, ++i) {
if (S[i] == 'I') {
for (int j = 0, cur = 0; j < N - i; ++j) dp2[j] = cur = (cur + dp[j]) % mod;
} else {
for (int j = N - i - 1, cur = 0; j >= 0; --j) dp2[j] = cur = (cur + dp[j + 1]) % mod;
}
}
return dp[0];
}
};
-
class Solution { public int numPermsDISequence(String S) { final int MODULO = 1000000007; int length = S.length(); int[][] dp = new int[length + 1][length + 2]; dp[0][0] = 1; for (int i = 1; i <= length; i++) { if (S.charAt(i - 1) == 'D') { for (int j = i - 1; j >= 0; j--) dp[i][j] = (dp[i][j + 1] + dp[i - 1][j]) % MODULO; } else { for (int j = 1; j <= i; j++) dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % MODULO; } } int permutations = 0; for (int i = 0; i <= length + 1; i++) permutations = (permutations + dp[length][i]) % MODULO; return permutations; } }
-
// OJ: https://leetcode.com/problems/valid-permutations-for-di-sequence/ // Time: O(N^2) // Space: O(N) // Ref: https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/168278/C%2B%2BJavaPython-DP-Solution-O(N2) class Solution { public: int numPermsDISequence(string S) { int N = S.size(), mod = 1e9 + 7; vector<int> dp(N + 1, 1), dp2(N); for (int i = 0; i < N; dp = dp2, ++i) { if (S[i] == 'I') { for (int j = 0, cur = 0; j < N - i; ++j) dp2[j] = cur = (cur + dp[j]) % mod; } else { for (int j = N - i - 1, cur = 0; j >= 0; --j) dp2[j] = cur = (cur + dp[j + 1]) % mod; } } return dp[0]; } };