903. Valid Permutations for DI Sequence Hard

1/**
2 * [903] Valid Permutations for DI Sequence
3 *
4 * You are given a string s of length n where s[i] is either:
5 * 
6 * 	'D' means decreasing, or
7 * 	'I' means increasing.
8 * 
9 * 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:
10 * 
11 * 	If s[i] == 'D', then perm[i] > perm[i + 1], and
12 * 	If s[i] == 'I', then perm[i] < perm[i + 1].
13 * 
14 * Return the number of valid permutations perm. Since the answer may be large, return it modulo 10^9 + 7.
15 *  
16 * Example 1:
17 * 
18 * Input: s = "DID"
19 * Output: 5
20 * Explanation: The 5 valid permutations of (0, 1, 2, 3) are:
21 * (1, 0, 3, 2)
22 * (2, 0, 3, 1)
23 * (2, 1, 3, 0)
24 * (3, 0, 2, 1)
25 * (3, 1, 2, 0)
26 * 
27 * Example 2:
28 * 
29 * Input: s = "D"
30 * Output: 1
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	n == s.length
36 * 	1 <= n <= 200
37 * 	s[i] is either 'I' or 'D'.
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/valid-permutations-for-di-sequence/
43// discuss: https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn num_perms_di_sequence(s: String) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_903() {
61    }
62}
63