Algorithm

Problem Name: 903. Valid Permutations for DI Sequence

Problem Link: https://leetcode.com/problems/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'
 

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const numPermsDISequence = function(s) {
  const mod = 1e9 + 7
  const n = s.length
  const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0))
  s = '#' + s
  dp[0][0] = 1
  for(let i = 1; i  < = n; i++) {
    const ch = s[i]
    for(let j = 0; j  < = i; j++) {
      if(ch === 'I') {
        for(let k = 0; k < j; k++) {
          dp[i][j] += dp[i - 1][k]
          dp[i][j] %= mod
        }
      } else {
        for(let k = j; k  <  i; k++) {
          dp[i][j] += dp[i - 1][k]
          dp[i][j] %= mod
        }
      }
    }
  }
  
  
  let res = 0
  
  for(let i = 0; i  < = n; i++) {
    res = (res + dp[n][i]> % mod
  }
  
  return res
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
s = "DID"

Output

x
–
+
cmd
5

#2 Code Example with Python Programming

Code - Python Programming


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        dp = [1] * (len(S) + 1)
        for c in S:
            if c == "I":
                dp = dp[:-1]
                for i in range(1, len(dp)):
                    dp[i] += dp[i - 1]
            else:
                dp = dp[1:]
                for i in range(len(dp) - 1)[::-1]:
                    dp[i] += dp[i + 1]
        return dp[0] % (10**9 + 7)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
s = "DID"

Output

x
–
+
cmd
5
Advertisements

Demonstration

Previous
#902 Leetcode Numbers At Most N Given Digit Set Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#904 Leetcode Fruit Into Baskets Solution in C, C++, Java, JavaScript, Python, C# Leetcode