[Java/Python 3] DP - longest common subsequence w/ brief explanation and analysis.
Q & A:\n\nQ: Can you please explain more how exactly lcs with its reverse helps?\nA: An example could be illustrative. e.g., "mbadm". Let\'s mark the characters
**Q & A:**\n\nQ: Can you please explain more how exactly lcs with its reverse helps?\nA: An example could be illustrative. e.g., "mbadm". Let\'s mark the characters not in LCS:\n"m`b`a`d`m"\nReverse:\n"m`d`a`b`m"\nWe need at least 2 insertions - `b` and `d` - to make them palindromes:\n"m`bd`a`db`m" or\n"m`db`a`bd`m"\n\n**End of Q & A**\n\n----\n\nPlease refer to my solution [Java/Python 3 2 Clean DP codes of O(m * n) & O(min(m, n)) space w/ breif explanation and analysis](https://leetcode.com/problems/max-dot-product-of-two-subsequences/discuss/649858/JavaPython-3-2-Clean-DP-codes-of-O(mn)-and-O(min(m-n))-space-w-breif-explanation-and-analysis.) of a similar problem: [1458. Max Dot Product of Two Subsequences](https://leetcode.com/problems/max-dot-product-of-two-subsequences/description/)\n\nMore similar LCS problems:\n[1092. Shortest Common Supersequence](https://leetcode.com/problems/shortest-common-supersequence/) and [Solution](https://leetcode.com/problems/shortest-common-supersequence/discuss/312757/JavaPython-3-O(mn)-clean-DP-code-w-picture-comments-and-analysis.)\n[1062. Longest Repeating Substring](https://leetcode.com/problems/longest-repeating-substring/) (Premium).\n[516. Longest Palindromic  Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/)\n[1312. Minimum Insertion Steps to Make a String Palindrome](https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/discuss/470709/JavaPython-3-DP-longest-common-subsequence-w-brief-explanation-and-analysis)\n\n----\nFind the size of the longest common subsequence between the original string and its reverse, deduct it from the size of the original string, that is the solution.\n```java\n    public int minInsertions(String s) {\n        String r = new StringBuilder(s).reverse().toString();\n        return s.length() - lcs(s, r);\n    }\n    private int lcs(String s, String r) {\n        int n = s.length();\n        int[][] dp = new int[n + 1][n + 1];\n        for (int i = 0; i < n; ++i)\n            for (int j = 0; j < n; ++j)\n                dp[i + 1][j + 1] = s.charAt(i) == r.charAt(j) ? dp[i][j] + 1 : Math.max(dp[i + 1][j], dp[i][j + 1]);\n        return dp[n][n];        \n    }\n\n```\n\n```python\n    def minInsertions(self, s: str) -> int:\n        def lcs(s: str, r: str) -> int:\n            n = len(r)\n            dp = [[0] * (n + 1) for _ in range(n + 1)]\n            for i, a in enumerate(s):\n                for j, b in enumerate(r):\n                    dp[i + 1][j + 1] = dp[i][j] + 1 if a == b else max(dp[i][j + 1], dp[i + 1][j])\n            return dp[n][n]\n        return len(s) - lcs(s, s[::-1])\n```\n**Analysis:**\nTime & space: `O(n ^ 2)`, where n = `s.length()`.\n\n----\n\nSpace optimization:\n\n```java\n    public int minInsertions(String s) {\n        return s.length() - lcs(s, new StringBuilder(s).reverse().toString());\n    }\n    private int lcs(String s, String r) {\n        int n = s.length();\n        int[][] dp = new int[2][n + 1];\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                dp[1 - i % 2][j + 1] = s.charAt(i) == r.charAt(j) ? 1 + dp[i % 2][j] : Math.max(dp[1 - i % 2][j], dp[i % 2][j + 1]);\n            }\n        }\n        return dp[n % 2][n];        \n    }\n```\n```python\n    def minInsertions(self, s: str) -> int:\n        \n        def lcs(s: str, r: str) -> int:\n            n = len(s)\n            dp = [[0] * (n + 1) for _ in range(2)]\n            for i, c in enumerate(s):\n                for j, d in enumerate(r):\n                    dp[1 - i % 2][j + 1] = 1 + dp[i % 2][j] if c == d else max(dp[i % 2][j + 1], dp[1 - i % 2][j])\n            return dp[n % 2][n]\n        \n        return len(s) - lcs(s, s[:: -1])\n```\n**Analysis:**\nTime: `O(n ^ 2)`,  space: `O(n)`, where `n = s.length()`.\n
['Dynamic Programming', 'Java', 'Python3']