Minimum Insertion Steps to Make a String Palindrome
Given a string s. In one step you can insert any character at any index of the string.
Return the minimum number of steps to make s palindrome.
Examples
Input: "zzazz"
Output: 0
Input: "mbadm"
Output: 2
Hints
Consider that the problem can be reduced to finding the minimum number of insertions to make the string a palindrome, which is equivalent to the length of the string minus the length of the longest palindromic subsequence (LPS).
To find the LPS, observe that it is the same as the longest common subsequence (LCS) between the string and its reverse. Use dynamic programming to compute the LCS between `s` and `s[::-1]`.
Implement a 2D DP table where `dp[i][j]` represents the LCS length of the first `i` characters of `s` and the first `j` characters of the reversed string. Fill the table by comparing characters and taking the maximum of skipping a character in either string. The answer is `len(s) - dp[n][n]`.
Minimum Insertion Steps to Make a String Palindrome
Given a string `s`. In one step you can insert any character at any index of the string.