Java | DP | 10 lines | Clean & simple code
Intuition\n Describe your first thoughts on how to solve this problem. \nIf we figure out the longest palindromic subsequence as per this leetcode problem, the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf we figure out the longest palindromic subsequence as per [this leetcode problem](https://leetcode.com/problems/longest-palindromic-subsequence/description/), the answer to the current problem should be the length of the string - the length of the longest palindromic subsequence. The rationale is that we can simply add a matching character for each existing character that is not part of the longest palindromic subsequence and make the entire string a palindrome.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n  public int minInsertions(String s) {\n    var n = s.length();\n    var dp = new int[n];\n    var dpPrev = new int[n];\n\n    for (var i = n-1; i >= 0; i--) {\n      dp[i] = 1;\n\n      for (var j = i+1; j < n; j++) {\n        dp[j] =\n          s.charAt(i) == s.charAt(j)\n          ? 2 + dpPrev[j-1]\n          : Math.max(dpPrev[j], dp[j-1]);        \n      }\n      dpPrev = dp.clone();\n    }\n    return n - dp[n-1];\n  }\n}\n```\nIf you like my solution, please upvote it!
['String', 'Dynamic Programming', 'Java']