Welcome to Subscribe On Youtube

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

Solutions

Solution 1: Dynamic Programming

We define $f[i][j]$ as the number of permutations that satisfy the problem’s requirements with the first $i$ characters of the string ending with the number $j$. Initially, $f[0][0]=1$, and the rest $f[0][j]=0$. The answer is $\sum_{j=0}^n f[n][j]$.

Consider $f[i][j]$, where $j \in [0, i]$.

If the $i$th character $s[i-1]$ is 'D', then $f[i][j]$ can be transferred from $f[i-1][k]$, where $k \in [j+1, i]$. Since $k-1$ can only be up to $i-1$, we move $k$ one place to the left, so $k \in [j, i-1]$. Therefore, we have $f[i][j] = \sum_{k=j}^{i-1} f[i-1][k]$.

If the $i$th character $s[i-1]$ is 'I', then $f[i][j]$ can be transferred from $f[i-1][k]$, where $k \in [0, j-1]$. Therefore, we have $f[i][j] = \sum_{k=0}^{j-1} f[i-1][k]$.

The final answer is $\sum_{j=0}^n f[n][j]$.

The time complexity is $O(n^3)$, and the space complexity is $O(n^2)$. Here, $n$ is the length of the string.

We can optimize the time complexity to $O(n^2)$ using prefix sums. Additionally, we can optimize the space complexity to $O(n)$ using a rolling array.

Solution 2: Dynamic Programming

This implementation uses dynamic programming. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

Solution 3: Dynamic Programming

This implementation uses dynamic programming. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int numPermsDISequence(String s) {
          final int mod = (int) 1e9 + 7;
          int n = s.length();
          int[] f = new int[n + 1];
          f[0] = 1;
          for (int i = 1; i <= n; ++i) {
              int pre = 0;
              int[] g = new int[n + 1];
              if (s.charAt(i - 1) == 'D') {
                  for (int j = i; j >= 0; --j) {
                      pre = (pre + f[j]) % mod;
                      g[j] = pre;
                  }
              } else {
                  for (int j = 0; j <= i; ++j) {
                      g[j] = pre;
                      pre = (pre + f[j]) % mod;
                  }
              }
              f = g;
          }
          int ans = 0;
          for (int j = 0; j <= n; ++j) {
              ans = (ans + f[j]) % mod;
          }
          return ans;
      }
  }
  
  
  // Solution 2
  class Solution {
      public int numPermsDISequence(String s) {
          final int mod = (int) 1e9 + 7;
          int n = s.length();
          int[][] f = new int[n + 1][n + 1];
          f[0][0] = 1;
          for (int i = 1; i <= n; ++i) {
              int pre = 0;
              if (s.charAt(i - 1) == 'D') {
                  for (int j = i; j >= 0; --j) {
                      pre = (pre + f[i - 1][j]) % mod;
                      f[i][j] = pre;
                  }
              } else {
                  for (int j = 0; j <= i; ++j) {
                      f[i][j] = pre;
                      pre = (pre + f[i - 1][j]) % mod;
                  }
              }
          }
          int ans = 0;
          for (int j = 0; j <= n; ++j) {
              ans = (ans + f[n][j]) % mod;
          }
          return ans;
      }
  }
  
  
  
  // Solution 3
  class Solution {
      public int numPermsDISequence(String s) {
          final int mod = (int) 1e9 + 7;
          int n = s.length();
          int[] f = new int[n + 1];
          f[0] = 1;
          for (int i = 1; i <= n; ++i) {
              int pre = 0;
              int[] g = new int[n + 1];
              if (s.charAt(i - 1) == 'D') {
                  for (int j = i; j >= 0; --j) {
                      pre = (pre + f[j]) % mod;
                      g[j] = pre;
                  }
              } else {
                  for (int j = 0; j <= i; ++j) {
                      g[j] = pre;
                      pre = (pre + f[j]) % mod;
                  }
              }
              f = g;
          }
          int ans = 0;
          for (int j = 0; j <= n; ++j) {
              ans = (ans + f[j]) % mod;
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      int numPermsDISequence(string s) {
          const int mod = 1e9 + 7;
          int n = s.size();
          vector<int> f(n + 1);
          f[0] = 1;
          for (int i = 1; i <= n; ++i) {
              int pre = 0;
              vector<int> g(n + 1);
              if (s[i - 1] == 'D') {
                  for (int j = i; j >= 0; --j) {
                      pre = (pre + f[j]) % mod;
                      g[j] = pre;
                  }
              } else {
                  for (int j = 0; j <= i; ++j) {
                      g[j] = pre;
                      pre = (pre + f[j]) % mod;
                  }
              }
              f = move(g);
          }
          int ans = 0;
          for (int j = 0; j <= n; ++j) {
              ans = (ans + f[j]) % mod;
          }
          return ans;
      }
  };
  
  
  // Solution 2
  class Solution {
  public:
      int numPermsDISequence(string s) {
          const int mod = 1e9 + 7;
          int n = s.size();
          int f[n + 1][n + 1];
          memset(f, 0, sizeof(f));
          f[0][0] = 1;
          for (int i = 1; i <= n; ++i) {
              int pre = 0;
              if (s[i - 1] == 'D') {
                  for (int j = i; j >= 0; --j) {
                      pre = (pre + f[i - 1][j]) % mod;
                      f[i][j] = pre;
                  }
              } else {
                  for (int j = 0; j <= i; ++j) {
                      f[i][j] = pre;
                      pre = (pre + f[i - 1][j]) % mod;
                  }
              }
          }
          int ans = 0;
          for (int j = 0; j <= n; ++j) {
              ans = (ans + f[n][j]) % mod;
          }
          return ans;
      }
  };
  
  
  
  // Solution 3
  class Solution {
  public:
      int numPermsDISequence(string s) {
          const int mod = 1e9 + 7;
          int n = s.size();
          vector<int> f(n + 1);
          f[0] = 1;
          for (int i = 1; i <= n; ++i) {
              int pre = 0;
              vector<int> g(n + 1);
              if (s[i - 1] == 'D') {
                  for (int j = i; j >= 0; --j) {
                      pre = (pre + f[j]) % mod;
                      g[j] = pre;
                  }
              } else {
                  for (int j = 0; j <= i; ++j) {
                      g[j] = pre;
                      pre = (pre + f[j]) % mod;
                  }
              }
              f = move(g);
          }
          int ans = 0;
          for (int j = 0; j <= n; ++j) {
              ans = (ans + f[j]) % mod;
          }
          return ans;
      }
  };
  
  

• class Solution:
      def numPermsDISequence(self, s: str) -> int:
          mod = 10**9 + 7
          n = len(s)
          f = [1] + [0] * n
          for i, c in enumerate(s, 1):
              pre = 0
              g = [0] * (n + 1)
              if c == "D":
                  for j in range(i, -1, -1):
                      pre = (pre + f[j]) % mod
                      g[j] = pre
              else:
                  for j in range(i + 1):
                      g[j] = pre
                      pre = (pre + f[j]) % mod
              f = g
          return sum(f) % mod
  
  
  # Solution 2
  class Solution:
      def numPermsDISequence(self, s: str) -> int:
          mod = 10**9 + 7
          n = len(s)
          f = [[0] * (n + 1) for _ in range(n + 1)]
          f[0][0] = 1
          for i, c in enumerate(s, 1):
              pre = 0
              if c == "D":
                  for j in range(i, -1, -1):
                      pre = (pre + f[i - 1][j]) % mod
                      f[i][j] = pre
              else:
                  for j in range(i + 1):
                      f[i][j] = pre
                      pre = (pre + f[i - 1][j]) % mod
          return sum(f[n][j] for j in range(n + 1)) % mod
  
  
  
  # Solution 3
  class Solution:
      def numPermsDISequence(self, s: str) -> int:
          mod = 10**9 + 7
          n = len(s)
          f = [1] + [0] * n
          for i, c in enumerate(s, 1):
              pre = 0
              g = [0] * (n + 1)
              if c == "D":
                  for j in range(i, -1, -1):
                      pre = (pre + f[j]) % mod
                      g[j] = pre
              else:
                  for j in range(i + 1):
                      g[j] = pre
                      pre = (pre + f[j]) % mod
              f = g
          return sum(f) % mod
  
  

• func numPermsDISequence(s string) (ans int) {
  	const mod = 1e9 + 7
  	n := len(s)
  	f := make([]int, n+1)
  	f[0] = 1
  	for i := 1; i <= n; i++ {
  		pre := 0
  		g := make([]int, n+1)
  		if s[i-1] == 'D' {
  			for j := i; j >= 0; j-- {
  				pre = (pre + f[j]) % mod
  				g[j] = pre
  			}
  		} else {
  			for j := 0; j <= i; j++ {
  				g[j] = pre
  				pre = (pre + f[j]) % mod
  			}
  		}
  		f = g
  	}
  	for j := 0; j <= n; j++ {
  		ans = (ans + f[j]) % mod
  	}
  	return
  }
  
  
  // Solution 2
  func numPermsDISequence(s string) (ans int) {
  	const mod = 1e9 + 7
  	n := len(s)
  	f := make([][]int, n+1)
  	for i := range f {
  		f[i] = make([]int, n+1)
  	}
  	f[0][0] = 1
  	for i := 1; i <= n; i++ {
  		pre := 0
  		if s[i-1] == 'D' {
  			for j := i; j >= 0; j-- {
  				pre = (pre + f[i-1][j]) % mod
  				f[i][j] = pre
  			}
  		} else {
  			for j := 0; j <= i; j++ {
  				f[i][j] = pre
  				pre = (pre + f[i-1][j]) % mod
  			}
  		}
  	}
  	for j := 0; j <= n; j++ {
  		ans = (ans + f[n][j]) % mod
  	}
  	return
  }
  
  
  
  // Solution 3
  func numPermsDISequence(s string) (ans int) {
  	const mod = 1e9 + 7
  	n := len(s)
  	f := make([]int, n+1)
  	f[0] = 1
  	for i := 1; i <= n; i++ {
  		pre := 0
  		g := make([]int, n+1)
  		if s[i-1] == 'D' {
  			for j := i; j >= 0; j-- {
  				pre = (pre + f[j]) % mod
  				g[j] = pre
  			}
  		} else {
  			for j := 0; j <= i; j++ {
  				g[j] = pre
  				pre = (pre + f[j]) % mod
  			}
  		}
  		f = g
  	}
  	for j := 0; j <= n; j++ {
  		ans = (ans + f[j]) % mod
  	}
  	return
  }
  
  

• function numPermsDISequence(s: string): number {
      const n = s.length;
      let f: number[] = Array(n + 1).fill(0);
      f[0] = 1;
      const mod = 10 ** 9 + 7;
      for (let i = 1; i <= n; ++i) {
          let pre = 0;
          const g: number[] = Array(n + 1).fill(0);
          if (s[i - 1] === 'D') {
              for (let j = i; j >= 0; --j) {
                  pre = (pre + f[j]) % mod;
                  g[j] = pre;
              }
          } else {
              for (let j = 0; j <= i; ++j) {
                  g[j] = pre;
                  pre = (pre + f[j]) % mod;
              }
          }
          f = g;
      }
      let ans = 0;
      for (let j = 0; j <= n; ++j) {
          ans = (ans + f[j]) % mod;
      }
      return ans;
  }
  
  
  // Solution 2
  function numPermsDISequence(s: string): number {
      const n = s.length;
      const f: number[][] = Array(n + 1)
          .fill(0)
          .map(() => Array(n + 1).fill(0));
      f[0][0] = 1;
      const mod = 10 ** 9 + 7;
      for (let i = 1; i <= n; ++i) {
          let pre = 0;
          if (s[i - 1] === 'D') {
              for (let j = i; j >= 0; --j) {
                  pre = (pre + f[i - 1][j]) % mod;
                  f[i][j] = pre;
              }
          } else {
              for (let j = 0; j <= i; ++j) {
                  f[i][j] = pre;
                  pre = (pre + f[i - 1][j]) % mod;
              }
          }
      }
      let ans = 0;
      for (let j = 0; j <= n; ++j) {
          ans = (ans + f[n][j]) % mod;
      }
      return ans;
  }
  
  
  
  // Solution 3
  function numPermsDISequence(s: string): number {
      const n = s.length;
      let f: number[] = Array(n + 1).fill(0);
      f[0] = 1;
      const mod = 10 ** 9 + 7;
      for (let i = 1; i <= n; ++i) {
          let pre = 0;
          const g: number[] = Array(n + 1).fill(0);
          if (s[i - 1] === 'D') {
              for (let j = i; j >= 0; --j) {
                  pre = (pre + f[j]) % mod;
                  g[j] = pre;
              }
          } else {
              for (let j = 0; j <= i; ++j) {
                  g[j] = pre;
                  pre = (pre + f[j]) % mod;
              }
          }
          f = g;
      }
      let ans = 0;
      for (let j = 0; j <= n; ++j) {
          ans = (ans + f[j]) % mod;
      }
      return ans;
  }
  
  

All Problems

All Solutions