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

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

# Minimum Insertions to Make a String Palindrome

## Problem Description

Given a string `s`, the task is to find the minimum number of insertions required to make `s` a palindrome. In one step, you can insert any character at any index of the string. A palindrome is a string that reads the same backward as forward.

**Example 1:**

Input: s = "zzazz" Output: 0 Explanation: The string "zzazz" is already a palindrome, so no insertions are needed.

**Example 2:**

Input: s = "mbadm" Output: 2 Explanation: The string can be transformed into "mbdadbm" or "mdbabdm" with two insertions.

**Example 3:**

Input: s = "leetcode" Output: 5 Explanation: Inserting 5 characters transforms the string into "leetcodocteel".

## 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 approach is highly inefficient due to the exponential number of possibilities.  For each position in the string, we could insert any character.  This makes the time complexity prohibitively large for even moderate-sized strings.

## Optimal Approach (Dynamic Programming)

The optimal approach involves using dynamic programming. The key idea is to find the length of the longest palindromic subsequence (LPS) in the string. The minimum number of insertions needed to make the string a palindrome is then the difference between the string's length and the length of the LPS.

Here's the algorithm:

1.  **Define DP Table:** Create a 2D array `dp` where `dp[i][j]` stores the length of the LPS of the substring `s[i...j]`. The dimensions of the `dp` table are `n x n`, where `n` is the length of the string `s`.
2.  **Base Case:** For substrings of length 1 (i.e., `i == j`), the LPS length is 1.  Therefore, `dp[i][i] = 1` for all `i`.
3.  **Recursive Relation:** Iterate through the substrings in increasing order of length.  For each substring `s[i...j]`:
    *   If `s[i] == s[j]`, then `dp[i][j] = dp[i+1][j-1] + 2`.  This means that if the characters at the start and end of the substring are equal, we add 2 to the LPS length of the substring without those characters.
    *   If `s[i] != s[j]`, then `dp[i][j] = max(dp[i+1][j], dp[i][j-1])`.  This means that if the characters at the start and end of the substring are not equal, we take the maximum LPS length of the substrings obtained by either removing the first character or the last character.
4.  **Result:** The length of the LPS of the entire string is `dp[0][n-1]`. The minimum number of insertions needed is `n - dp[0][n-1]`.

```python
def min_insertions_palindrome(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2:
                    dp[i][j] = 2
                else:
                    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]

# Example Usage
s1 = "zzazz"
print(f'Min insertions for {s1}: {min_insertions_palindrome(s1)}') # Output: 0

s2 = "mbadm"
print(f'Min insertions for {s2}: {min_insertions_palindrome(s2)}') # Output: 2

s3 = "leetcode"
print(f'Min insertions for {s3}: {min_insertions_palindrome(s3)}') # Output: 5

Big(O) Run-time Analysis

The dynamic programming approach has a time complexity of O(n^2), where n is the length of the string. This is because we need to fill an n x n DP table, and each cell can be filled in O(1) time.

Big(O) Space Usage Analysis

The space complexity is also O(n^2) because we are using a 2D array of size n x n to store the intermediate results.

Edge Cases

1. Empty String: If the input string is empty, the function should return 0 because an empty string is considered a palindrome.
2. Single Character String: If the input string has only one character, it is also a palindrome, so the function should return 0.
3. Palindrome String: If the input string is already a palindrome, the function should correctly return 0.
4. Long Strings: The algorithm should be able to handle strings up to the specified constraint (500 characters).