C# Using Longest Palindromic Subsequence
Approach\nUsing 516. Longest Palindromic Subsequence.\nIf we know the longest palindromic sub-sequence is x and the length of the string is n then, what is the 
# Approach\nUsing [516. Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/).\nIf we know the longest palindromic sub-sequence is x and the length of the string is $$n$$ then, what is the answer to this problem? It is $$n - x$$ as we need $$n - x$$ insertions to make the remaining characters also palindrome.\n\n\n# Complexity\n- Time complexity: $$O(n \\times m)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```\npublic class Solution\n{\n    private readonly Dictionary<(int i, int j), int> _cache = new();\n\n    public int MinInsertions(string s)\n    {\n        var reversedString = string.Join("", s.Reverse());\n        return s.Length - getLCS(s, 0, reversedString, 0);\n    }\n    \n    private int getLCS(string a, int i, string b, int j)\n    {\n        if (i >= a.Length || j >= b.Length)\n        {\n            return 0;\n        }\n\n        if (_cache.TryGetValue((i, j), out var value))\n        {\n            return value;\n        }\n\n        if (a[i] == b[j])\n        {\n            return _cache[(i, j)] = 1 + getLCS(a, i + 1, b, j + 1);\n        }\n\n        return _cache[(i, j)] = Math.Max(getLCS(a, i + 1, b, j), getLCS(a, i, b, j + 1));\n    }\n}\n```
['C#']