Minimum Insertion Steps to Make a String Palindrome

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 a palindrome.

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

For example:

• Input: s = "zzazz" Output: 0 Explanation: The string "zzazz" is already a palindrome we do not need any insertions.

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

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

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

## Problem Description

The problem asks to find the minimum number of insertions needed to make a given string `s` a palindrome. A palindrome is a string that reads the same forwards and backward. We need to determine the fewest characters to insert into `s` at any position to achieve this property.

## Naive Approach (Brute Force)

A brute-force approach would involve trying all possible insertion combinations and checking if the resulting string is a palindrome. However, this is extremely inefficient due to the exponential number of possible insertions.  For each position in the string, we could insert any character.  The complexity of this approach is prohibitively high for even moderately sized strings.

## Optimal Solution: Dynamic Programming

A more efficient approach uses dynamic programming.  The key idea is to find the longest palindromic subsequence (LPS) of the given string `s`. The number of insertions needed to make `s` a palindrome is equal to the difference between the length of `s` and the length of its LPS.

Let `dp[i][j]` be the length of the LPS of the substring `s[i...j]`. We can define the recurrence relation as follows:

1.  If `s[i] == s[j]`, then `dp[i][j] = dp[i+1][j-1] + 2`
2.  If `s[i] != s[j]`, then `dp[i][j] = max(dp[i+1][j], dp[i][j-1])`

The base case is when `i == j`, then `dp[i][j] = 1`.

Once we have the length of the LPS, say `lpsLength`, the minimum number of insertions is `s.length() - lpsLength`.

```java
class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        return n - dp[0][n - 1];
    }
}

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

        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

        return n - dp[0][n - 1]

Big(O) Run-time Analysis

The dynamic programming solution has a time complexity of O(n^2), where n is the length of the string. This is because we need to fill in the dp table, which has dimensions n x n, requiring us to iterate through all possible substrings.

Big(O) Space Usage Analysis

The space complexity is also O(n^2) because we store the dp table, which has dimensions n x n.

Edge Cases

1. Empty String: If the input string is empty, the number of insertions needed is 0.
2. Single Character String: If the input string contains only one character, it is already a palindrome, so the number of insertions needed is 0.
3. Already a Palindrome: If the input string is already a palindrome, the number of insertions needed is 0.
4. String with all same characters: For example, "aaaa". This is already a palindrome, so the number of insertions needed is 0.