Best O(N*M) Solution
Approach\nDP (Bottom Up Approach)\n\n# Complexity\n- Time complexity:\nO(n * m)\n\n- Space complexity:\nO(n * m)\n\n# Code\n\nclass Solution {\nprivate:\n    in
# Approach\nDP (Bottom Up Approach)\n\n# Complexity\n- Time complexity:\n$$O(n * m)$$\n\n- Space complexity:\n$$O(n * m)$$\n\n# Code\n```\nclass Solution {\nprivate:\n    int longestPalindromeSubseq(string s, string t) { \n        int n = s.length(); \n        vector<vector<int>> dp(n+1, vector<int>(n+1, 0));\n        for (int i = 0; i <= n; i++) {\n            dp[i][0] = 0;\n            dp[0][i] = 0;\n        } \n        for (int idx1 = 1; idx1 <= n; idx1++) {\n            for (int idx2 = 1; idx2 <= n; idx2++) {\n                if (s[idx1-1] == t[idx2-1])\n                    dp[idx1][idx2] = 1 + dp[idx1-1][idx2-1];\n                else\n                    dp[idx1][idx2] = max (dp[idx1-1][idx2], dp[idx1][idx2-1]);\n            }\n        }      \n        return dp[n][n];\n    }    \npublic:\n    int minInsertions(string s) {\n        int n = s.length();\n        string t = s;\n        reverse(t.begin(), t.end());\n        int lpsLen = longestPalindromeSubseq(s, t);\n        return n - lpsLen;\n    }\n};\n```
['C++']