🎯TLE -> DP approach (Using Two Pointers)✔
Intuition\n Describe your first thoughts on how to solve this problem. \nLet\'s say s="abscsdfa". The longest palindromic subsequence in this string is "ascsa".
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet\'s say s="abscsdfa". The longest palindromic subsequence in this string is "ascsa". So, the number of insertions required is `8 - 5 = 3`.\n\nSo we will first find longest palindromic subsequence and then will subtract from total length of string to get the desired answer.\n\n\n# Complexity\n- Time complexity: O(n^2)\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 Solution -- Got TLE\n```\nclass Solution {\n    int dfs(string &s, int i, int j){\n        if (i>j) \n            return 0;\n        if (i==j)\n            return 1;\n\n        if (s[i]==s[j]){\n            return 2 + dfs(s, i+1, j-1);\n        }\n        return max( dfs(s, i+1, j) , dfs(s, i, j-1) );\n    }\n\npublic:\n    int minInsertions(string s) {\n        int n = s.length();\n        return n - dfs(s, 0, n-1);\n    }\n};\n```\n.\n.\n# Recursive Solution -- With DP\n```C++ []\nclass Solution {\n    vector<vector<int>> dp;\n    int dfs(string &s, int i, int j){\n        if (i>j) \n            return 0;\n        if (i==j)\n            return 1;\n        \n        if (dp[i][j]^-1)  return dp[i][j];\n\n        if (s[i]==s[j]){\n            return dp[i][j] = 2 + dfs(s, i+1, j-1);\n        }\n        return dp[i][j] = max( dfs(s, i+1, j) , dfs(s, i, j-1) );\n    }\n\npublic:\n    int minInsertions(string s) {\n        int n = s.length();\n        dp.resize(n+1, vector<int> (n+1,-1));\n        return n - dfs(s, 0, n-1);\n    }\n};\n```\n\n\n\n
['Two Pointers', 'String', 'Dynamic Programming', 'C++']