903. Valid Permutations for DI Sequence LeetCode Solution

In this guide, you will get 903. Valid Permutations for DI Sequence LeetCode Solution with the best time and space complexity. The solution to Valid Permutations for DI Sequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Valid Permutations for DI Sequence solution in C++
Valid Permutations for DI Sequence solution in Java
Valid Permutations for DI Sequence solution in Python
Additional Resources

903. Valid Permutations for DI Sequence LeetCode Solution image

Problem Statement of Valid Permutations for DI Sequence

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’, then perm[i] > perm[i + 1], and
If s[i] == ‘I’, then perm[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.length
1 <= n <= 200
s[i] is either 'I' or 'D'.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

903. Valid Permutations for DI Sequence LeetCode Solution in C++

class Solution {
 public:
  int numPermsDISequence(string s) {
    constexpr int kMod = 1'000'000'007;
    const int n = s.length();
    // dp[i][j] := the number of valid permutations with i + 1 digits, where
    // s[i] is j-th Digit of remaining digits
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));

    // When there's only one digit, the number of permutations is 1.
    for (int j = 0; j <= n; ++j)
      dp[0][j] = 1;

    for (int i = 1; i <= n; ++i)
      if (s[i - 1] == 'I') {  // s[i - 1] == 'I'
        // Calculate the postfix sum to prevent duplicate calculation.
        int postfixsum = 0;
        for (int j = n - i; j >= 0; --j) {
          postfixsum = (postfixsum + dp[i - 1][j + 1]) % kMod;
          dp[i][j] = postfixsum;
        }
      } else {  // s[i - 1] == 'D'
        // Calculate the prefix sum to prevent duplicate calculation.
        int prefix = 0;
        for (int j = 0; j <= n - i; ++j) {
          prefix = (prefix + dp[i - 1][j]) % kMod;
          dp[i][j] = prefix;
        }
      }

    return dp[n][0];
  }
};
/* code provided by PROGIEZ */

903. Valid Permutations for DI Sequence LeetCode Solution in Java

class Solution {
  public int numPermsDISequence(String s) {
    final int kMod = 1_000_000_007;
    final int n = s.length();
    // dp[i][j] := the number of valid permutations with i + 1 digits, where s[i] is j-th
    // Digit of remaining digits
    int[][] dp = new int[n + 1][n + 1];

    // When there's only one digit, the number of permutations is 1.
    for (int j = 0; j <= n; ++j)
      dp[0][j] = 1;

    for (int i = 1; i <= n; ++i)
      if (s.charAt(i - 1) == 'I') { // s[i - 1] == 'I'
        // Calculate the postfix sum to prevent duplicate calculation.
        int postfixsum = 0;
        for (int j = n - i; j >= 0; --j) {
          postfixsum = (postfixsum + dp[i - 1][j + 1]) % kMod;
          dp[i][j] = postfixsum;
        }
      } else { // s[i - 1] == 'D'
        // Calculate the prefix sum to prevent duplicate calculation.
        int prefix = 0;
        for (int j = 0; j <= n - i; ++j) {
          prefix = (prefix + dp[i - 1][j]) % kMod;
          dp[i][j] = prefix;
        }
      }

    return dp[n][0];
  }
}
// code provided by PROGIEZ

903. Valid Permutations for DI Sequence LeetCode Solution in Python

class Solution {
 public:
  int numPermsDISequence(string s) {
    constexpr int kMod = 1'000'000'007;
    const int n = s.length();
    vector<int> dp(n + 1);

    // When there's only one digit, the number of permutations is 1.
    for (int j = 0; j <= n; ++j)
      dp[j] = 1;

    for (int i = 1; i <= n; ++i) {
      vector<int> newDp(n + 1);
      if (s[i - 1] == 'I') {  // s[i - 1] == 'I'
        // Calculate the postfix sum to prevent duplicate calculation.
        int postfixsum = 0;
        for (int j = n - i; j >= 0; --j) {
          postfixsum = (postfixsum + dp[j + 1]) % kMod;
          newDp[j] = postfixsum;
        }
      } else {  // s[i - 1] == 'D'
        // Calculate the prefix sum to prevent duplicate calculation.
        int prefix = 0;
        for (int j = 0; j <= n - i; ++j) {
          prefix = (prefix + dp[j]) % kMod;
          newDp[j] = prefix;
        }
      }
      dp = std::move(newDp);
    }

    return dp[0];
  }
};
 # code by PROGIEZ