Skip to content

903. Valid Permutations for DI Sequence 👍

Approach 1: 2D DP

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public int numPermsDISequence(String s) {
    final int MOD = 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]) % MOD;
          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]) % MOD;
          dp[i][j] = prefix;
        }
      }

    return dp[n][0];
  }
}

Approach 2: 1D DP

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public int numPermsDISequence(String s) {
    final int MOD = 1_000_000_007;
    final int n = s.length();
    int[] dp = new int[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) {
      int[] newDp = new int[n + 1];
      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[j + 1]) % MOD;
          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]) % MOD;
          newDp[j] = prefix;
        }
      }
      dp = newDp;
    }

    return dp[0];
  }
}