DP🫡| Simple Java Solution | Longest Palindromic Subsequence
Intuition\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 ne
# Intuition\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# Approach\nWe just need to find the length of **longest common subsequence** of the given string and the string obtained by reversing the original string.\n\n# Complexity\n- Time complexity: O(N^2) \n\n- Space complexity: O(N^2)\n\n# Code\n```\nclass Solution {\n    public int minInsertions(String a) {\n        StringBuilder s = new StringBuilder(a);\n        s.reverse();\n        // Obtaining the reverse of original string\n        String b = s.toString();\n        \n        int n = a.length();\n        int t[][] = new int[n+1][n+1];\n        \n        // Top-down DP\n        for(int i=1; i<=n; i++) \n            for(int j=1; j<=n; j++)\n                if(a.charAt(i-1)==b.charAt(j-1)) t[i][j] = 1 + t[i-1][j-1];\n                else t[i][j] = Math.max(t[i-1][j], t[i][j-1]);\n        // Desired answer\n        return n-t[n][n];\n    }\n}\n```
['String', 'Dynamic Programming', 'Java']