Problem statement

https://leetcode.com/problems/valid-permutations-for-di-sequence/

Solution

There is solution with O(n^3) time and O(n^2) space complexity, using dp and divide and conquer ideas. Let dfs(i, j) be answer for S[i:j] and ask question: where is 0 in our sequence? There can be 3 cases:

  1. Sequence starts with I, then 0 can be in the beginning and we have dfs(i + 1, j) options.
  2. Sequence ends with D, then 0 can be in the end and we have dfs(i, j - 1) options.
  3. 0 in the middle, and we are looking for DI. Imagine we have IDI|DI|DII, then what we can state is the following: we need to solve problem for IDI and for DII parts. Also we need to multiply it by number of combinations: here C_8^4: this is how many ways we have to choose set of number for left part (number for right part will be chosen automatically)

Complexity

It is O(n^3) for time and O(n^2) for space.

Code

class Solution:
    def numPermsDISequence(self, S):
        n, N = len(S), 10**9 + 7
        
        @lru_cache(None)
        def dfs_comb(i, j):
            if j == 0 or i == j: return 1
            return (dfs_comb(i-1, j) + dfs_comb(i-1, j-1)) % N
        
        @lru_cache(None)
        def dfs(i, j):
            if j <= i + 1: return 1
            ans = 0
            if S[j-1] == "D": ans += dfs(i, j - 1)
            if S[i] == "I"  : ans += dfs(i + 1, j)
            for l in range(i, j - 1):
                if S[l:l+2] == "DI":
                    ans += dfs(i,l) * dfs(l+2,j) * dfs_comb(j-i, l+1-i)
            return ans % N
        
        return dfs(0, n)

Remark

There is also O(n^2) time solution: define by dp[i][j] number of permutations of 0, 1, ..., i-1 which ends with j, it also be the number of answers for s[:i] which ends with j. Then we have:

  1. if s[i-1] == "I" then dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j-1]
  2. if s[i-1] == "D" then dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + ... + dp[i-1][i-1]

Imagine each time when appending the j to the previous permutations, you have to add 1 to each number in the previous permutation which is greater than or equals to j. In this way, we keep the orders and counts of previous permutations and cumulate.

eg. We already have permutation (1, 0, 3, 2). We are trying to append 2. Now the (1, 0, 3, 2) changes to (1, 0, 4, 3) then appended with a 2. We have (1, 0, 4, 3, 2). Although the values change but the order and count don’t change.

Also we need to keep cumulative prefixes and sufixes to make it O(n^2).