C++, DP, tabulation, space optimized, simple
Intuition\n\n\n* Check longest common subsequence between string s and it\'s reverse string t.\n* len(s) - lcs(s, t) will be the number of non-matching characte
# Intuition\n\n```\n* Check longest common subsequence between string s and it\'s reverse string t.\n* len(s) - lcs(s, t) will be the number of non-matching characters.\n* Hence we need to add those many characters.\n```\n\n# Tabulation (Not space optimized)\n```\nclass Solution {\npublic:\n    int minInsertions(string s) {\n        string t = s; reverse(t.begin(), t.end()); \n        int n = s.size();\n        return n - lcs(s, t, n);\n    }\n\nprivate:\n    int lcs(string& s, string& t, int& n) {\n        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));\n\n        for (int i = 1; i <= n; i++) {\n            for (int j = 1; j <= n; j++) {\n                if (s[i-1] == t[j-1]) dp[i][j] = 1 + dp[i-1][j-1];\n                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);\n            }\n        }\n\n        return dp[n][n];\n    }\n};\n```\n\n# Tabulation (Space optimized)\n```\nclass Solution {\npublic:\n    int minInsertions(string s) {\n        int n = s.size();\n        return n - lcs(s, n);\n    }\n\nprivate:\n    int lcs(string& s, int& n) {\n        vector<int> prev(n + 1, 0);\n        vector<int> curr(n + 1, 0);\n\n        for (int i = 1; i <= n; i++) {\n            for (int j = 1; j <= n; j++) {\n                if (s[i-1] == s[n-j]) curr[j] = 1 + prev[j-1];\n                else curr[j] = max(prev[j], curr[j-1]);\n            }\n            prev = curr;\n        }\n\n        return prev[n];\n    }\n};\n```
['String', 'Dynamic Programming', 'C++']