Leetcode 1312. Minimum Insertion Steps to Make a String Palindrome

Problem statement

https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/

Solution

Just use dp(i, j) be answer for substring s[i:j+1]. If s[i] == s[j], then return dp(i + 1, j - 1). In the opposite case we either remove i-th or j-th.

Complexity

Time complexity is O(n^2) as well as space.

Code

class Solution:
    def minInsertions(self, s):
        @lru_cache(None)
        def dp(i, j):
            if j <= i: return 0
            if s[i] == s[j]: return dp(i + 1, j - 1)
            return min(dp(i + 1, j), dp(i, j - 1)) + 1
        
        return dp(0, len(s) - 1)