903. Valid Permutations for DI Sequence

Description

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 permutationsperm. 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'.

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n²)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const numPermsDISequence = function (s) {
  const MODULO = 10 ** 9 + 7;
  const n = s.length;
  let dp = new Array(n + 1).fill(1);

  const calculateDecPerms = remain => {
    const nexDp = new Array(n + 1).fill(0);
    let prefixSum = 0;

    for (let index = remain - 1; index >= 0; index--) {
      prefixSum = (prefixSum + dp[index + 1]) % MODULO;
      nexDp[index] = prefixSum;
    }
    return nexDp;
  };

  const calculateIncPerms = remain => {
    const nexDp = new Array(n + 1).fill(0);
    let prefixSum = 0;

    for (let index = 0; index < remain; index++) {
      prefixSum = (prefixSum + dp[index]) % MODULO;
      nexDp[index] = prefixSum;
    }
    return nexDp;
  };

  for (let index = 0; index < n; index++) {
    const isDec = s[index] === 'D';
    const remain = n - index;

    dp = isDec ? calculateDecPerms(remain) : calculateIncPerms(remain);
  }
  return dp[0];
};