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".)

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', then P[i] > P[i+1], and;
  • If S[i] == 'I', then P[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. 1 <= S.length <= 200
  2. 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];
    }
};

Java

  • 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];
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions