Minimum Insertion Steps To Make A String Palindrome - Leetcode Solution

Problem:

Given a string "s", find the minimum number of characters that need to be inserted to make it a palindrome.

A palindrome is a string that reads the same backward as forward.

Example 1: Input: s = "aab" Output: 1 Explanation: The palindrome can be "aba" or "baab".

Example 2: Input: s = "leetcode" Output: 5 Explanation: The palindrome can be "leetcodocteel".

Solution:

The problem can be solved using dynamic programming. We can create a two-dimensional array dp where dp[i][j] represents the minimum number of insertions needed to make the substring s[i..j] a palindrome. We can fill up the dp array iteratively from the smaller substring to larger substring.

Base case: For a string s of length n, the dp array will be filled in the following order:

1. For i = n-1 to 0: a. For j = i to n-1: If i==j, dp[i][j]=0; If s[i]==s[j], dp[i][j]=dp[i+1][j-1]; If s[i]!=s[j], dp[i][j]=1+min(dp[i+1][j], dp[i][j-1]);

Explanation:

1. We start filling the dp array from the smaller substring to larger substring.
2. For a single character s[i], the substring s[i..i] is already a palindrome with zero insertions.
3. When the substring s[i..j] contains two or more characters: a. If s[i]==s[j], then the substring s[i..j] is already a palindrome and we don't need to insert any characters. So we can directly update dp[i][j] = dp[i+1][j-1]; b. If s[i]!=s[j], then we need to insert either s[i] or s[j] to make the substring s[i..j] a palindrome. So we can choose either to insert s[i] before s[j] or insert s[j] before s[i] to make it a palindrome. Therefore, the minimum number of insertions required will be 1 + min(dp[i+1][j], dp[i][j-1]).

Finally, the minimum number of insertion required to make the entire string s a palindrome will be stored at dp[0][n-1].

Time Complexity: O(n^2), where n is the length of the string.

Space Complexity: O(n^2), where n is the length of the string.

Below is the Python code for the same:

class Solution: def minInsertions(self, s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)]

    # base case
    for i in range(n-1, -1, -1):
        for j in range(i, n):
            if i == j:
                dp[i][j] = 0
            elif s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])

    return dp[0][n-1]

1