Leetcode 903. Valid Permutations for DI Sequence
Problem explanation
We are given a string of n
letters 'D' or 'I' and our job is to find a permutation for the numbers between 0
and n
that matches with the string. The rules of the permutation is that a 'D' would mean the number before is greater than the one after and 'I' means the number before is less than the one after.
An example can be that for the string "DID", the resulting permutations can be (1, 0, 3, 2), (2, 0, 3, 1), (2, 1, 3, 0), (3, 0, 2, 1), (3, 1, 2, 0), totaling 5
. The idea is to return the amount of valid permutations the string can generate.
Solution explanation
Let dp[i][j]
be the number of valid permutations with i + 1
digits, where the i
th character is the j
th largest unused digit. This is a 2D dynamic programming solution that builds up the number valid permutations bearing in mind the constraints of the problem.
If the i
th character is 'I', then we sum the values of dp[i - 1][k]
for all k >= j
.
If the i
th character is 'D', then we sum the values of dp[i - 1][k]
for all k < j
.
To speed up this process, we can calculate prefix and postfix sums of the dp
array.
Algorithm Steps
The algorithm follows these main steps:
- First we initialize our dp table. All row and column will be filled with zeros except for the first row as we are sure when we have one character we will always have a permutation.
- We then build our dp table. In this table, for each character in the string we build accumulating prefix sums if the character is a 'D' or postfix (backward) sum for an 'I'. In order to do this we loop starting from
i = 1
up ton
. For each iteration ofi
, check if thei-1
character in the string is an 'I': 3. If the character is an 'I', then we are looking for increasing permutations. We start by initializing a postfixSum to zero and enter a loop fromj = n - i
down to zero. We then: adddp[i - 1][j + 1]
to the postfix sum and then store the postfix sum indp[i][j]
. 4. If the character is 'D', then we are looking for decreasing permutations. Initialize a variable prefix to 0. Loopj
from zero ton - i
. Then: adddp[i - 1][j]
to prefix and store prefix indp[i][j]
. - Finally, return the first value of the last row in the dp table.
Python Solution
1 2python 3class Solution: 4 def numPermsDISequence(self, s: str) -> int: 5 MOD = 10**9 + 7 6 n = len(s) 7 dp = [[0] * (n + 1) for _ in range(n + 1)] 8 9 # when there's only one digit, the number of permutations is 1 10 for j in range(n + 1): 11 dp[0][j] = 1 12 13 for i in range(1, n + 1): 14 if s[i - 1] == 'I': 15 # Calculate postfix sum to prevent duplicate calculation 16 postfix_sum = 0 17 for j in range(n - i, -1, -1): 18 postfix_sum = (postfix_sum + dp[i - 1][j + 1]) % MOD 19 dp[i][j] = postfix_sum 20 else: 21 # Calculate prefix sum to prevent duplicate calculation 22 prefix_sum = 0 23 for j in range(n - i + 1): 24 prefix_sum = (prefix_sum + dp[i - 1][j]) % MOD 25 dp[i][j] = prefix_sum 26 return dp[n][0]
Java Solution
1 2java 3import java.util.Arrays; 4 5class Solution { 6 private static final int MOD = 1_000_000_007; 7 public int numPermsDISequence(String s) { 8 int n = s.length(); 9 int[][] dp = new int[n + 1][n + 1]; 10 11 // when there's only one digit, the number of permutations is 1 12 Arrays.fill(dp[0], 1); 13 14 for (int i = 1; i <= n; i++) { 15 if (s.charAt(i - 1) == 'I') { 16 int postfixSum = 0; 17 for (int j = n - i; j >= 0; j--) { 18 postfixSum = (postfixSum + dp[i - 1][j + 1]) % MOD; 19 dp[i][j] = postfixSum; 20 } 21 } else { 22 int prefixSum = 0; 23 for (int j = 0; j <= n - i; j++) { 24 prefixSum = (prefixSum + dp[i - 1][j]) % MOD; 25 dp[i][j] = prefixSum; 26 } 27 } 28 } 29 return dp[n][0]; 30 } 31}
C++ Solution
1 2cpp 3class Solution { 4public: 5 int numPermsDISequence(string S) { 6 int n = S.size(), mod = 1e9+7; 7 vector<vector<int>> dp(n+1, vector<int> (n+1, 0)); 8 9 // when there's only one digit, the number of permutations is 1 10 for (int j = 0; j <= n; j++) dp[0][j] = 1; 11 12 for (int i = 1; i <= n; i++) 13 if (S[i-1] == 'I') { 14 int tmp = 0; 15 for (int j = n - i ; j >= 0; --j) { 16 tmp = (tmp + dp[i - 1][j + 1]) % mod; 17 dp[i][j] = tmp; 18 } 19 } else { 20 int tmp = 0; 21 for (int j = 0; j <= n - i; ++j) { 22 tmp = (tmp + dp[i - 1][j]) % mod; 23 dp[i][j] = tmp; 24 } 25 } 26 return dp[n][0]; 27 } 28};
C# Solution
1 2csharp 3public class Solution { 4 public int NumPermsDISequence(string s) { 5 int n = s.Length; 6 int mod = 1000000007; 7 8 var dp = new int[n + 1, n + 1]; 9 10 // when there's only one digit, the number of permutations is 1 11 for (int j = 0; j <= n; j++) 12 dp[0, j] = 1; 13 14 for (int i = 1; i <= n; i++) 15 if (s[i - 1] == 'I') { 16 int tmp = 0; 17 for (int j = n - i; j >= 0; --j) { 18 tmp = (tmp + dp[i - 1, j + 1]) % mod; 19 dp[i, j] = tmp; 20 } 21 } else { 22 int tmp = 0; 23 for (int j = 0; j <= n - i; ++j) { 24 tmp = (tmp + dp[i - 1, j]) % mod; 25 dp[i, j] = tmp; 26 } 27 } 28 29 return dp[n, 0]; 30 } 31}
JavaScript Solution
1 2javascript 3var numPermsDISequence = function(s) { 4 const MOD = 1e9 + 7; 5 const n = s.length; 6 let dp = Array.from(Array(n + 1), () => Array(n + 1).fill(0)); 7 8 // when there's only one digit, the number of permutations is 1 9 for (let j = 0; j <= n; j++) 10 dp[0][j] = 1; 11 12 for(let i = 1; i <= n; i++) 13 if(s.charAt(i - 1) == 'I') { 14 let sum = 0; 15 for(let j = n - i; j >= 0; j--) { 16 sum = (sum + dp[i - 1][j + 1]) % MOD; 17 dp[i][j] = sum; 18 } 19 } else { 20 let sum = 0; 21 for(let j = 0; j <= n - i; j++) { 22 sum = (sum + dp[i - 1][j]) % MOD; 23 dp[i][j] = sum; 24 } 25 } 26 return dp[n][0]; 27};
Applications & Conclusions
The problem involves arranging a permutation that fits a specific pattern represented by a string composed of 'D's and 'I's. It demonstrates a practical use of dynamic programming, a strategy often used in algorithms related to optimization or counting. Understanding the problem and solution can help improve your skill in handling array operations, dynamic programming, permutation explore, and the usage of prefix or postfix sum technique.
This problem can be applied in different problems such as scheduling or arranging tasks, ordering a list of data, and so on. Additionally, techniques used in this problem can be utilized in other more complex combinatory problems, such as those involving permutation and combinations, tasks scheduling, project sequencing, and more.
While the solution itself may not be directly implementable in many practical scenarios due to its specific nature, the process of finding the solution provides good practice in understanding the concept behind dynamic programming and postfix and prefix cumulative sums. The solution might seem tedious due to the deep nested loop, but with a good understanding of dynamic programming, arriving at the optimal solution would be much easier.
In data structures and algorithms, understanding how to break down problems into smaller subproblems that can be built up to arrive at the grand solution is a crucial skill. It also demonstrates how problems can be solved by considering previously solved subproblems rather than starting from scratch.
Overall, understanding this problem could be very beneficial, given you took time to understand not just the solution, but also the thought process behind arriving at the optimal solution. The implementation could be done in different programming languages including Python, Java, JavaScript and C#, promoting good practice for multilingual programmers.
While the problem is related to finding a permutation that satisfies a represented condition, the knowledge and skills gained from understanding the problem are applicable in other combinatorics problems and other disciplines.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.