1312. Minimum Insertion Steps to Make a String Palindrome

This is the daily challenge on 22/Apr/2023.

Idea

To solve this problem, there is one key point that we can’t miss.

Assume x is the length of the longest palindromic subsequence, and n is the length of s, the result is simply n-x

This is because for those chars that are not in the longest palindromic subsequence, we have to add one char for each of them to make them palindromic.

Now this problem turns into another(arguably easier) problem 516. Longest Palindromic Subsequence.

You can find the detailed solution in the above link.

Algorithm

This problem changes only one line of code from the solution of 516. Longest Palindromic Subsequence.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def minInsertions(self, s: str) -> int:
        @functools.cache
        def dp(l,r):
            if l==r:
                return 1
            if r-l==1:
                return 2 if s[r]==s[l] else 1
            if s[r]==s[l]:
                return 2+dp(l+1,r-1)
            return max(dp(l+1,r),dp(l,r-1))
        return len(s)-dp(0,len(s)-1)