JAVA | DP | Well Explained🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nMy first intuition was that the no. of insertions needed to make the string palindromic
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMy first intuition was that the no. of insertions needed to make the string palindromic would be **same as the no. of deletions** required to make the string palindromic. suppose we have the string ***abbca***. \n\nEither we can add c to make it palindromic ***acbbca*** or we can remove c to make it palindromic ***abba***.\n\nNow the question has reduced to [Find the Longest Palindromic subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/description/). Then subtract the length of LPS from the actual length of the string.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIn the above example :\n- length of the LPS -> ***abba*** = 4\n- length of the actual string ***abbca*** = 5\n- ans -> 5 - 4 = 1\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nwe are iterating the string n times for each character. So the time complexity would be $$O(n^2)$$.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nWe are using 2D array for DP. So the space complexity is $$O(n^2)$$.\nIt can further be reduced to $$O(n)$$ as for a particular moment we are just using the above row to make use to DP. We just need to rows instead of the whole DP array. *For the sake for simplicity I have used 2D array (you can try and further optimise it to $$O(n)$$).*\n\n# Code\n```\nclass Solution {\n\n    public int solve(String s) {\n        int[][] dp = new int[s.length() + 1][s.length() + 1];\n        String sr = (new StringBuilder(s)).reverse().toString();\n\n        for(int i = 1; i <= s.length(); i++) {\n            for(int j = 1; j <= s.length(); j++) {\n                char a = s.charAt(i - 1);\n                char b = sr.charAt(j - 1);\n                if(a == b) {\n                    dp[i][j] = dp[i - 1][j - 1] + 1;\n                } else {\n                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n                }\n            }\n        }\n        return dp[s.length()][s.length()];\n    }\n\n    public int minInsertions(String s) {\n        return s.length() - solve(s);\n    }\n}\n```
['Dynamic Programming', 'Java']