[Java/C++/Python] Longest Common Sequence
Intuition\nSplit the string s into to two parts,\nand we try to make them symmetrical by adding letters.\n\nThe more common symmetrical subsequence they have,\n
## **Intuition**\nSplit the string `s` into to two parts,\nand we try to make them symmetrical by adding letters.\n\nThe more common symmetrical subsequence they have,\nthe less letters we need to add.\n\nNow we change the problem to find the length of longest common sequence.\nThis is a typical dynamic problem.\n<br>\n\n## **Explanation**\n**Step1.**\nInitialize `dp[n+1][n+1]`,\nwhere`dp[i][j]` means the length of longest common sequence between\n`i` first letters in `s1` and `j` first letters in `s2`.\n\n**Step2.**\nFind the the longest common sequence between `s1` and `s2`,\nwhere `s1 = s` and `s2 = reversed(s)`\n\n**Step3.**\n`return n - dp[n][n]`\n<br>\n\n## **Complexity**\nTime `O(N^2)`\nSpace `O(N^2)`\n<br>\n\n**Java:**\n```java\n    public int minInsertions(String s) {\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) == s.charAt(n - 1 - j) ? dp[i][j] + 1 : Math.max(dp[i][j + 1], dp[i + 1][j]);\n        return n - dp[n][n];\n    }\n```\n\n**C++:**\n```cpp\n    int minInsertions(string s) {\n        int n = s.length();\n        vector<vector<int>> dp(n + 1, vector<int>(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[i] == s[n - 1 - j] ? dp[i][j] + 1 : max(dp[i][j + 1], dp[i + 1][j]);\n        return n - dp[n][n];\n    }\n```\n\n**Python:**\nNote that `~j = -j - 1`\n```python\n    def minInsertions(self, s):\n        n = len(s)\n        dp = [[0] * (n + 1) for i in xrange(n + 1)]\n        for i in xrange(n):\n            for j in xrange(n):\n                dp[i + 1][j + 1] = dp[i][j] + 1 if s[i] == s[~j] else max(dp[i][j + 1], dp[i + 1][j])\n        return n - dp[n][n]\n```\n
[]