23.04.22 Today’s Leetcode

1312. Minimum Insertion Steps to Make a String Palindrome (hard)

Failed at 22/45

class Solution:
    def minInsertions(self, s: str) -> int:
        res = math.inf
        n = len(s)
        mid = n // 2
        a, b = Counter(), Counter(s)

        def help(a, b):
            c = a + b
            temp = 0
            for key in c.keys():
                temp += abs(a[key] - b[key])
            return temp

        for i in range(n):
            char = s[i]
            b[char] -= 1
            res = min(res, help(a, b))
            a[char] += 1
            res = min(res, help(a, b))

        return res

DP Approach

class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        dp = [0] * n
        for i in range(n - 2, -1, -1):
            prev = 0
            for j in range(i + 1, n):
                temp = dp[j]
                if s[i] == s[j]:
                    dp[j] = prev
                else:
                    dp[j] = min(dp[j], dp[j - 1]) + 1
                prev = temp
        return dp[n - 1]