C# | Runtime beats 91.07%, Memory beats 82.14% [EXPLAINED]
Intuition\nTo make a string a palindrome, you can think of adding characters to balance it out. A palindrome reads the same forwards and backwards. If some char
# Intuition\nTo make a string a palindrome, you can think of adding characters to balance it out. A palindrome reads the same forwards and backwards. If some characters don\u2019t match, we need to add characters to make them match, which means we need to figure out how many additions are necessary.\n\n# Approach\nDynamic Programming: We use a table to keep track of the minimum insertions needed for each substring of the string.\n\nTwo Pointers: For every substring, if the characters at both ends match, we check the substring inside. If they don\'t match, we decide to insert either character and take the minimum of the two cases.\n\nFill the Table: Start with shorter substrings and build up to the entire string, using previous results to fill in the current one.\n\n# Complexity\n- Time complexity:\nO(n2) because we check all possible substrings.\n\n- Space complexity:\nO(n2) due to the table storing results for each substring.\n\n# Code\n```csharp []\npublic class Solution\n{\n    public int MinInsertions(string s)\n    {\n        int n = s.Length;\n        // dp[i][j] will hold the minimum number of insertions needed to make the substring s[i..j] a palindrome\n        int[,] dp = new int[n, n];\n\n        for (int length = 2; length <= n; length++)\n        {\n            for (int i = 0; i <= n - length; i++)\n            {\n                int j = i + length - 1; // End index of the current substring\n                if (s[i] == s[j])\n                {\n                    dp[i, j] = dp[i + 1, j - 1]; // Characters match, no insertions needed\n                }\n                else\n                {\n                    dp[i, j] = Math.Min(dp[i + 1, j], dp[i, j - 1]) + 1; // Insert either character\n                }\n            }\n        }\n        \n        return dp[0, n - 1]; // The result for the entire string\n    }\n}\n\n```
['Two Pointers', 'Matrix', 'C#']