903. Valid Permutations for DI Sequence

Approach 1: 2D DP

• Time: $O(n^2)$
• Space: $O(n^2)$

C++Java

class Solution {
 public:
  int numPermsDISequence(string s) {
    constexpr int kMod = 1'000'000'007;
    const int n = s.length();
    // dp[i][j] := # of valid permutations w/ 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 # of perms 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 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 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];
  }
};

class Solution {
  public int numPermsDISequence(String s) {
    final int kMod = 1_000_000_007;
    final int n = s.length();
    // dp[i][j] := # of valid permutations w/ 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 # of perms 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 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 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];
  }
}

Approach 2: 1D DP

• Time: $O(n^2)$
• Space: $O(n)$

C++Java

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 # of perms 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 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 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 = move(newDp);
    }

    return dp[0];
  }
};

class Solution {
  public int numPermsDISequence(String s) {
    final int kMod = 1_000_000_007;
    final int n = s.length();
    int[] dp = new int[n + 1];

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

    for (int i = 1; i <= n; ++i) {
      int[] newDp = new int[n + 1];
      if (s.charAt(i - 1) == 'I') { // s[i - 1] == 'I'
        // Calculate 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 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 = newDp;
    }

    return dp[0];
  }
}