Python recursive solution(Time out and just for reference)
\nclass Solution(object):\n    def numPermsDISequence(self, S):\n        """\n        :type S: str\n        :rtype: int\n        """\n        n = len(S)\n      
```\nclass Solution(object):\n    def numPermsDISequence(self, S):\n        """\n        :type S: str\n        :rtype: int\n        """\n        n = len(S)\n        \n        def helper(S, D, I):\n            if S == \'\': return 1\n            sign = S[0]\n            S = S[1:]\n            \n            count = 0\n            if sign == \'D\':\n                for i, d in enumerate(D):\n                    count += helper(S, D[:i], D[i + 1:] + I)\n            else:\n                for i, d in enumerate(I):\n                    count += helper(S, D + I[:i], I[i + 1:])\n                    \n            return count\n            \n        count = 0\n        nums = [i for i in range(n + 1)]\n        for i in range(n + 1):\n            count += helper(S, nums[:i], nums[i + 1:])\n            \n        return count\n            \n```
[]