✅Easiest Approach || RECURSIVE -> MEMOIZATION || Jai Shree Ram🚩🚩
Approach and Intuition\n- Visualising all the possible permuations and returning only valid ones\n- Taking a prev value which checks the prev value taken , now 
# Approach and Intuition\n- Visualising all the possible permuations and returning only valid ones\n- Taking a prev value which checks the prev value taken , now if prev is -1 this means we can taking any integer .\n- If `s[i] == \'I\'` then we need to take only that element which is not visited yet and is `> than prev` one and vice versa for `s[i] == \'D\'`.\n- Our base case tells whether valid permutation is formed or not.\n- We have taken bool vis array because while one recursive call we do not want to repeat same elements and so we are marking vis elements and `backtracking` vis elements as not visited.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $O(N^3)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(N^2)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# RECURSIVE (TLE)\n```JAVA []\nclass Solution {\n    boolean[] vis;\n    int mod = (int)1e9+7;\n    public int numPermsDISequence(String s) {\n        vis = new boolean[s.length()+2];\n        return solve(s,0,-1);\n    }\n    private int solve(String s,int idx,int prev){\n        if(idx >= s.length()){\n            return 1;\n        }\n\n        int cnt = 0;\n        for(int i=0;i<=s.length();i++){\n            if(!vis[i]){\n                vis[i] = true;\n                if(prev == -1){\n                    cnt = (cnt + solve(s,idx,i)) % mod;\n                } else if((s.charAt(idx) == \'D\' && i < prev) \n                    || s.charAt(idx) == \'I\' && i > prev){\n                    cnt = (cnt + solve(s,idx+1,i)) % mod;\n                }\n                vis[i] = false;\n            }\n        }\n\n        return cnt;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<bool> vis;\n    int mod = (int)1e9+7;\n    int n;\n    int solve(string s,int idx,int prev){\n        if(idx >= n){\n            return 1;\n        }\n\n        int cnt = 0;\n        for(int i=0;i<=n;i++){\n            if(!vis[i]){\n                vis[i] = true;\n                if(prev == -1){\n                    cnt = (cnt + solve(s,idx,i)) % mod;\n                } else if((s[idx] == \'D\' && i < prev) \n                    || s[idx] == \'I\' && i > prev){\n                        \n                    cnt = (cnt + solve(s,idx+1,i)) % mod;\n                }\n                vis[i] = false;\n            }\n        }\n\n        return cnt;\n    }\n    int numPermsDISequence(string s) {\n        n = s.size();\n        vis = vector<bool> (n + 2 , false);\n        return solve(s,0,-1);\n    }\n};\n```\n```Python []\nclass Solution:\n    def __init__(self):\n        self.vis = []\n        self.mod = int(1e9 + 7)\n        self.n = 0\n\n    def solve(self, s, idx, prev):\n        if idx >= self.n:\n            return 1\n\n        cnt = 0\n        for i in range(self.n + 1):\n            if not self.vis[i]:\n                self.vis[i] = True\n                if prev == -1 or (s[idx] == \'D\' and i < prev) or (s[idx] == \'I\' and i > prev):\n                    cnt = (cnt + self.solve(s, idx + 1, i)) % self.mod\n                self.vis[i] = False\n\n        return cnt\n\n    def numPermsDISequence(self, s: str) -> int:\n        self.n = len(s)\n        self.vis = [False] * (self.n + 2)\n        return self.solve(s, 0, -1)\n\n```\n\n# MEMOIZATION\n```JAVA []\nclass Solution {\n    boolean[] vis;\n    Integer[][] memo;\n    int mod = (int)1e9+7;\n    public int numPermsDISequence(String s) {\n        vis = new boolean[s.length()+2];\n        memo = new Integer[s.length()][s.length()+3];\n        return solve(s,0,-1);\n    }\n    private int solve(String s,int idx,int prev){\n        if(idx >= s.length()){\n            return 1;\n        } else if(memo[idx][prev+1] != null){\n            return memo[idx][prev+1];\n        }\n\n        int cnt = 0;\n        for(int i=0;i<=s.length();i++){\n            if(!vis[i]){\n                vis[i] = true;\n                if(prev == -1){\n                    cnt = (cnt + solve(s,idx,i)) % mod;\n                } else if((s.charAt(idx) == \'D\' && i < prev) \n                    || s.charAt(idx) == \'I\' && i > prev){\n                        \n                    cnt = (cnt + solve(s,idx+1,i)) % mod;\n                }\n                vis[i] = false;\n            }\n        }\n\n        return memo[idx][prev+1] = cnt;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<bool> vis;\n    vector<vector<int>> dp;\n    int mod = (int)1e9+7;\n    int n;\n    int solve(string s,int idx,int prev){\n        if(idx >= n){\n            return 1;\n        } if(dp[idx][prev+1] != -1){\n            return dp[idx][prev+1];\n        }\n\n        int cnt = 0;\n        for(int i=0;i<=n;i++){\n            if(!vis[i]){\n                vis[i] = true;\n                if(prev == -1){\n                    cnt = (cnt + solve(s,idx,i)) % mod;\n                } else if((s[idx] == \'D\' && i < prev) \n                    || s[idx] == \'I\' && i > prev){\n                        \n                    cnt = (cnt + solve(s,idx+1,i)) % mod;\n                }\n                vis[i] = false;\n            }\n        }\n\n        return dp[idx][prev+1] = cnt;\n    }\n    int numPermsDISequence(string s) {\n        n = s.size();\n        vis = vector<bool> (n + 2 , false);\n        dp = vector<vector<int>> (n + 1 , vector<int>(n + 3, -1));\n        return solve(s,0,-1);\n    }\n};\n```\n```Python []\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        memo = {}\n        vis = [False] * (len(s) + 2)\n        mod = 10**9 + 7\n\n        def solve(idx, prev):\n            if idx >= len(s):\n                return 1\n            if (idx, prev) in memo:\n                return memo[(idx, prev)]\n\n            cnt = 0\n            for i in range(len(s) + 1):\n                if not vis[i]:\n                    vis[i] = True\n                    if prev == -1 or (s[idx] == \'D\' and i < prev) or (s[idx] == \'I\' and i > prev):\n                        cnt = (cnt + solve(idx + 1, i)) % mod\n                    vis[i] = False\n\n            memo[(idx, prev)] = cnt\n            return cnt\n\n        return solve(0, -1)\n\n```\n\n
['Dynamic Programming', 'Backtracking', 'Recursion', 'Python', 'C++', 'Java', 'Python3']