Problem description:

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.

A Palindrome String is one that reads the same backward as well as forward.

Example 1:

1
2
3
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

Example 2:

1
2
3
Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

1
2
3
Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Solution:

Let’s imagine matching the characters of the string like a palindrome, from the begining and the end with 2 pointers i and j.We may encounter 2 scenarios:

  1. The character at i matches character at j.
  2. The characters don’t match each other

In case of 1 we just increase the pointer i and decrease the pointer j, i++ and j-- respectively.

In the second case we have 2 options:

  1. Insert one character at j to match the character at i.

Or

  1. Insert one character at i to match the character at j.

Since we are not actually adding the characters in the string but just calculating the cost,In case 1 we increase the pointer i by 1 and j stays as it is, as we still need a character to match at jand in case 2 we decrease the pointer j by 1 and i stays as it is, as we still need a character to match at i.both the cases adds cost 1 since we are inserting a letter.

We can then use these two different pairs of new i and j values (i+1, j and i, j-1) to again repeat the process and use the minimum result of these as our result for current pair of i, j.We can see that this is recursive and thus we can use recursion with caching to store the repeated values.

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minInsertions(self, s: str) -> int:
        # find longest common sequence for s and reversed(s)
        n = len(s)
        dp = [[0]*(n+1) for i in range(n+1)]
        
        for i in range(n):
            for j in range(n):
                dp[i+1][j+1] = dp[i][j] + 1 if s[i] == s[~j] else max(dp[i+1][j], dp[i][j+1])
        return n - dp[n][n]

time complexity: $O()$
space complexity: $O()$
reference:
related problem: