Editorial-like solution, simple to understand with multiple approaches from Brute-force to optimal
The problem asks what is the number of valid permutations that follow a string of "DI" instructions, if a number i is used in a podition with \'D\' the next num
The problem asks what is the number of valid permutations that follow a string of `"DI"` instructions, if a number `i` is used in a podition with `\'D\'` the next number must be in the range `0 <= j < i`, likewise if it\'s in an `\'I\'` position the next number must be `i < j <= n` where `n` is the length if the string provided, the hard part comes in that we cannot repeat the same number, so it seems (but turns out not to be the case) that we need to remember all the previous numbers to solve the problem, let\'s see how we might develop a solution.\n\n\n# Approach #1: Brute-Force\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe first thing that is recommended to be done in a complex problem like this one is to generate all possible solutions and discard the invalid ones, that can be done via backtracking, we define a helper function `backTrack` that keeps track of where in the string we are and what was the previous number used, and define a set `state` that contains all numbers previously used; at a given index position `i` we check for all numbers bigger/smaller than the previous number, if we can insert it into the permutation we add it to the stack, we we are done generating all it\'s sub-solutions we remove it from the set, (this can also be done with a stack, which may be faster).\nIf we reach `i == n` we finished generating a permutation and add `1` to our count (which I named `ans`).\n\n# Algorithm\n<!-- Describe your approach to solving the problem. -->\n1. Define a set/stack and a counter\n2. Define the `backTrack` function:\n2.1 If we reached the end, increase the counter\n2.2 If not, go through all numbers lower/higher than the previous number and check if they can be added, if yes then add the number tot the set, call `backTrack` with `i+1` and this added number, when the function returns, remove the number from the set\n3. Call `backTrack` for all possible starting number `0` to `n`\n\n# Complexity\n- Time complexity: $$O(n!)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nAt any index `i` we have `i` options to choose from in worst-case, since `n` can go up to `200` this will result in a TLE.\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nWe use a set/stack that will contain at most `n` numbers when a permutation is complete\n\n# Implementation (only python, sorry)\n```\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        n = len(s)\n        ans = [0]\n        state = set()\n        def backTrack(i, p):\n            if i == n:\n                ans[0] += 1\n                return\n            if s[i] == "I":\n                for j in range(p+1, n+1):\n                    if j not in state:\n                        state.add(j)\n                        backTrack(i+1, j)\n                        state.remove(j)\n            else:\n                for j in range(0, p):\n                    if j not in state:\n                        state.add(j)\n                        backTrack(i+1, j)\n                        state.remove(j)\n            return  \n        for i in range(n+1):\n            state.add(i)\n            backTrack(0, i)\n            state.remove(i)\n        return ans[0]%(10**9+7)\n```\n\n# Approach #2: Dynamic programming\n\n# Intuition\nThe previous solution was too slow to be accepted, we need to find a faster way to calculate the answer. We first note that we got asked the number of valid permutations, so maybe (for this problem to be possible, we definitely) we don\'t need to generate all possible permutations to know how many there are, usually we can break down a problem into sub-problems to generate an answer faster from solving sub-problems\nAt first it may look like this is impossible to do here, since at each index the number we choose will affect all the possible choices in the future, but remembering we only need to know the quantity we may wonder if maybe the quantities are not dependent directly on the number you choose to place, let\'s do a thought experiment, imagine instead of using the numbers `(1,2,3,4, ...)` to generate our permutatons we use `(1,1,1,1, ...)` only a bunch of ones, and when we use a number like `3` the whole thing turns into `(1,1,0,1, ...)` so we have a certain concept of "order" so that the problem is the same, now think about using `1` or `2` or `3`, in a given index `i` we would get accordingly `(0,1,1,1), (1,0,1,1), (1,1,0,1)` which are different, but look very similar! Why they all look so similar? because they all have the same idea of **relative ordering**, `1` is still smaller than `3` and `4` even when 2 is out of the equation and likewise for all the others, so if we only focus on the relative ordering of the numbers essentially all of the three sub-problems above are **identical**, so we can just represent them all as `(1,1,1)`.\nThis is still not the complete picture, we know that the `"ID"` will limit our choice of next number, so returning to the last example, if the digit is `\'I\'`, then in the case of choosing `1` we would have `(0,1,1,1)` and the next number could be any of the following ones, but if we chose `2` the the sub-problem is `(1,0,1,1)` and we can only choose as the next number the ones to the right of the new zero, likewise if it were a `\'D\'` it would be the ones to the left of the zero, with that in mind we can now define our dynamic programming sub-problem.\n\n`\ndp[i][j] = Solution to sub-problem s[i:n], if we can choose only ones bounded to the j\'th one\n`\n\nBy bounded I mean that if `s[i]` is `\'I\'` we can choose the ones from the `j` one to the right-end and if it is a `\'D\'` we can choose the ones from `j` one to the left-end.\nFor example `dp[2][3]` for the tuple `(1,1,1,1,1,1,1)` is the solution to the sub-string `s[2:n]` using at position `2` any one that is from the inclusive left/right (depending on `s[2]`) of the highlighted one in `(1,1,_1_,1,1)`, notice that the size of the tuple is smaller by 2 than the original because we zero\'ed two other ones in the original tuple, in general, if the original tuple is of size `n`, at index `i` the tuple will have size `n-i`.\n\nNow that we have a table, let\'s see how we can generate answers from sub-problems. The base case is very simple, `s[n-1]` is either `\'I\'` or `\'D\'` and the tuple is simply `(1,1)`, we can define the base cases as follows:\n```\nif s[n-1] == \'I\':\n    #If we choose 1, then it is impossible to increase\n    dp[n-1][0] = 1\n    dp[n-1][1] = 0\nelif s[n-1] == \'D:\n    #If we choose 0, then it is impossible to decrease\n    dp[n-1][0] = 0\n    dp[n-1][1] = 1\n```\nThis idea of choosing the highest number or the lowest, makes it impossible to continue will keep re-occurring in later cases too.\nFor an index `i < n-1` we know that if `s[i] == \'I\'` then the last number will have an answer of zero, if `s[i] == \'D\'` then the first number will have an answer of zero, in general `dp[i][j]\n` will have all the answers that were pre-calculated in that row `i` (from the definition of the dp) and will also contain all the possible answers of the sub-problem at the `i+1` using only one to the left/right of it, which in our table happens that answer turns out to be stored in `dp[i+1][j]` (you can convince yourself of that by imagining how removing a one from a tuple changes the absolute postion of each remaining one), so our final update step looks like this.\n\n```\nif s[n-1] == \'I\':\n    if i == n-1:\n        #If we choose 1, then it is impossible to increase\n        dp[n-1][0] = 1\n        dp[n-1][1] = 0\n    else:\n        if j == n-i:\n            dp[i][j] = 0\n        else:\n            dp[i][j] = dp[i][j+1] + dp[i+1][j]\nelif s[n-1] == \'D:\n    if i == n-1:\n        #If we choose 0, then it is impossible to decrease\n        dp[n-1][0] = 0\n        dp[n-1][1] = 1\n    else:\n        if j == 0:\n            dp[i][j] = 0\n        else:\n            dp[i][j] = dp[i][j-1] + dp[i+1][j]\n```\nPhew! That\'s a pretty complicated update step, make sure you understand it, before writing it down because later on it will get worse! Now at last all that\'s left to do is to write down the solution\n\n# Algorithm\n1. Define our table `dp`\n2. Go from the base case to the original case\n3. Update the table according to the update step\n4. return the `sum` of all possible start choices\n\n# Implementation (only python, sorry)\n```\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        n = len(s)\n        dp = [[None for j in range(n-i+1)] for i in range(n)]\n        for j in range(n-1, 0-1, -1):\n            if s[j] == "I":\n                if j == n-1:\n                    dp[j][0] = 1\n                    dp[j][1] = 0\n                else:\n                    dp[j][n-j] = 0\n                    for i in range((n-j)-1, 0-1, -1):\n                        dp[j][i] = dp[j+1][i]+dp[j][i+1]\n            else:\n                if j == n-1:\n                    dp[j][0] = 0\n                    dp[j][1] = 1\n                else:\n                    dp[j][0] = 0\n                    for i in range(1, n-j+1):\n                        dp[j][i] = dp[j+1][i-1]+dp[j][i-1]\n        return sum([dp[0][i] for i in range(n+1)])%(10**9+7)\n```\n# Complexity\n- Time complexity: $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nIt only takes $O(1)$ to calculate the update step, we have `n + n-1 + n-2 + ... ` entries in the table, so $n^2$ time to compute every entry.\n\n- Space complexity: $$O(n^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe table has size $n^2$\n\n# Approach 3 DP + Double buffer\n\nWe notice that the update step only makes use of the last computed row and the current row being computed, so we can use two arrays and to calculate the whole ordeal, the space complexity will then be $O(n)$\n```\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        n = len(s)\n        dp = None\n        for j in range(n-1, 0-1, -1):\n            ndp = [None for i in range(n-j+1)]\n            if s[j] == "I":\n                if j == n-1:\n                    ndp[0] = 1\n                    ndp[1] = 0\n                else:\n                    ndp[n-j] = 0\n                    for i in range((n-j)-1, 0-1, -1):\n                        ndp[i] = dp[i]+ndp[i+1]\n            else:\n                if j == n-1:\n                    ndp[0] = 0\n                    ndp[1] = 1\n                else:\n                    ndp[0] = 0\n                    for i in range(1, n-j+1):\n                        ndp[i] = dp[i-1]+ndp[i-1]\n            dp = ndp\n        return sum(dp)%(10**9+7)\n```\n\n# Approach 4 Optimized memory\n\nWe can make a solution with only one array, first notice that the update step of `\'I\'` is fairly easy to adapt to one array since the base case is in a completely new index, but in the `\'D` case we need to update `i=0` so we set a variable `last` to remember the last value removed, but we need the last variable to update the next entry so we define an `nlast` to remember the variable that is about to be updated so that we can then update last with the  value that was before the update, whew... (see the code, it\'s easier to understand)\n\n```\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        n = len(s)\n        dp = [0 for _ in range(n+1)]\n        for j in range(n-1, 0-1, -1):\n            if s[j] == "I":\n                if j == n-1:\n                    dp[0] = 1\n                    dp[1] = 0\n                else:\n                    dp[n-j] = 0\n                    for i in range((n-j)-1, 0-1, -1):\n                        dp[i] = dp[i]+dp[i+1]\n            else:\n                if j == n-1:\n                    dp[0] = 0\n                    dp[1] = 1\n                else:\n                    last = dp[0]\n                    dp[0] = 0\n                    for i in range(1, n-j+1):\n                        nlast = dp[i]\n                        dp[i] = last+dp[i-1]\n                        last = nlast\n        return sum(dp)%(10**9+7)\n```\n\nAny comments or improvements are appreciated, thank you for reading!
['Python3']