# Minimum Insertion Steps to Make a String Palindrome
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome)
Canonical: https://scaleengineer.com/dsa/problems/minimum-insertion-steps-to-make-a-string-palindrome
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
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.

# Approaches
## Brute-Force Recursion
A straightforward recursive approach that directly models the problem. For any substring, if the ends match, we solve for the inner substring. If they don't, we try inserting a character at either end and take the minimum of the two resulting subproblems.
**Time:** O(2^n), where n is the length of the string. In the worst-case scenario (a string with no matching characters), each call to `solve` for a substring of length `k` generates two calls for substrings of length `k-1`, leading to an exponential number of function calls. · **Space:** O(n), where n is the length of the string. This is due to the maximum depth of the recursion stack.
**Pros:** Simple to understand and implement.; Directly translates the problem's definition into code.
**Cons:** Extremely inefficient due to a large number of redundant computations for the same subproblems.; Will result in a 'Time Limit Exceeded' error for all but the smallest input sizes.
### Explanation
This approach solves the problem by breaking it down into smaller, overlapping subproblems. We define a function `solve(s, i, j)` that computes the minimum insertions for the substring `s[i...j]`. The logic follows a simple decision process at each step. If the characters at the current endpoints `i` and `j` are the same, they form a palindromic pair, and we only need to solve the problem for the substring between them, `s[i+1...j-1]`. If they are different, we must perform an insertion. We can either insert a character to match `s[i]` or a character to match `s[j]`. This means we either solve for `s[i+1...j]` or `s[i...j-1]` and add one to the result for the insertion. We choose the option that yields the minimum number of insertions. The base case for the recursion is an empty or single-character string, which is already a palindrome and requires zero insertions.

```java
class Solution {
    public int minInsertions(String s) {
        return solve(s, 0, s.length() - 1);
    }

    private int solve(String s, int i, int j) {
        if (i >= j) {
            return 0;
        }
        if (s.charAt(i) == s.charAt(j)) {
            return solve(s, i + 1, j - 1);
        } else {
            return 1 + Math.min(solve(s, i + 1, j), solve(s, i, j - 1));
        }
    }
}
```
### Algorithm
- Define a recursive function `solve(s, i, j)` which returns the minimum insertions for the substring `s[i...j]`.
- **Base Case:** If `i >= j`, the substring is empty or has one character. It's already a palindrome, so return 0.
- **Recursive Step:**
  - If `s.charAt(i) == s.charAt(j)`, the ends match. The problem reduces to the inner substring. Return `solve(s, i + 1, j - 1)`.
  - If `s.charAt(i) != s.charAt(j)`, the ends don't match. We must insert a character. We take the minimum of two choices:
    1. Make `s[i...j-1]` a palindrome and add a matching character for `s[j]`. Cost: `1 + solve(s, i, j - 1)`.
    2. Make `s[i+1...j]` a palindrome and add a matching character for `s[i]`. Cost: `1 + solve(s, i + 1, j)`.
    - Return `1 + min(solve(s, i + 1, j), solve(s, i, j - 1))`.

## Memoization (Top-Down DP)
This approach improves upon the brute-force recursion by using a memoization table (a 2D array) to store the results of subproblems. This avoids re-computation of the same subproblem, drastically reducing the time complexity.
**Time:** O(n^2). Each of the `n * n` possible subproblems is computed exactly once. The computation for each subproblem takes constant time. · **Space:** O(n^2) for the memoization table, plus O(n) for the recursion stack depth. The total space complexity is O(n^2).
**Pros:** Significantly more efficient than brute-force, with a polynomial time complexity.; Maintains the top-down, logical structure of the recursive solution.
**Cons:** Requires O(n^2) space for the memoization table, which can be significant for large n.; Still has the overhead associated with recursive function calls.
### Explanation
The brute-force recursive solution suffers from solving the same subproblems multiple times. We can optimize this by using dynamic programming with memoization. We'll use a 2D array, `memo`, where `memo[i][j]` will store the minimum insertions needed for the substring `s[i...j]`. The recursive function's logic remains the same, but with one key difference: at the beginning of the function, we check if the result for the current state `(i, j)` has already been computed. If `memo[i][j]` is not null, we return the stored value. Otherwise, we compute the result, store it in `memo[i][j]`, and then return it. This ensures that each of the `O(n^2)` possible subproblems is solved only once.

```java
class Solution {
    private Integer[][] memo;

    public int minInsertions(String s) {
        int n = s.length();
        memo = new Integer[n][n];
        return solve(s, 0, n - 1);
    }

    private int solve(String s, int i, int j) {
        if (i >= j) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        if (s.charAt(i) == s.charAt(j)) {
            memo[i][j] = solve(s, i + 1, j - 1);
        } else {
            memo[i][j] = 1 + Math.min(solve(s, i + 1, j), solve(s, i, j - 1));
        }
        return memo[i][j];
    }
}
```
### Algorithm
- Create a 2D array `memo[n][n]` to store the results of subproblems, initialized to a value like `null` or `-1`.
- Use the same recursive function `solve(s, i, j)` as the brute-force approach.
- Before computing the result for `(i, j)`, check if `memo[i][j]` already contains a valid result. If so, return it immediately.
- If not, compute the result using the same recursive logic.
- Store the computed result in `memo[i][j]` before returning it.

## Tabulation (Bottom-Up DP)
This approach uses an iterative, bottom-up method to solve the problem. It builds the solution from smaller subproblems to larger ones using a 2D DP table, avoiding recursion entirely. The recurrence relation is the same as in the previous approaches.
**Time:** O(n^2). The nested loops iterate through all `O(n^2)` subproblems, and each calculation is constant time. · **Space:** O(n^2) for the 2D DP table.
**Pros:** Avoids recursion overhead, which can make it slightly faster in practice than memoization.; Can be more intuitive for those who prefer iterative solutions.
**Cons:** Requires O(n^2) space, same as the memoization approach.
### Explanation
Instead of a top-down recursive approach, we can solve the problem iteratively in a bottom-up fashion. We use a 2D array `dp[n][n]`, where `dp[i][j]` stores the minimum insertions to make `s[i...j]` a palindrome. We fill this table for substrings of increasing length. Substrings of length 1 are already palindromes, so `dp[i][i] = 0`. We then compute the values for substrings of length 2, then 3, and so on, up to `n`. When calculating `dp[i][j]`, the values for the smaller subproblems it depends on (`dp[i+1][j-1]`, `dp[i+1][j]`, `dp[i][j-1]`) will have already been computed. The final result for the entire string `s[0...n-1]` is stored in `dp[0][n-1]`.

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

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}
```
### Algorithm
- Create a 2D DP table, `dp[n][n]`, where `dp[i][j]` will store the minimum insertions for `s[i...j]`.
- The base cases, `dp[i][i] = 0`, are implicitly handled by initializing the array with zeros.
- Iterate through substring lengths `len` from 2 to `n`.
- For each `len`, iterate through all possible start indices `i` from `0` to `n-len`.
- Calculate the end index `j = i + len - 1`.
- Apply the transition formula:
  - If `s[i] == s[j]`, then `dp[i][j] = dp[i+1][j-1]`.
  - If `s[i] != s[j]`, then `dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])`.
- The final answer is `dp[0][n-1]`.

## Space-Optimized Bottom-Up DP
This is the most efficient approach in terms of space. It's based on the key insight that the minimum number of insertions is equal to the length of the string minus the length of its Longest Palindromic Subsequence (LPS). We can then compute the LPS length using a space-optimized bottom-up DP, reducing space from O(n^2) to O(n).
**Time:** O(n^2). The time complexity is dominated by the nested loops. · **Space:** O(n) for the 1D DP array.
**Pros:** Most space-efficient solution.; Maintains the optimal O(n^2) time complexity.
**Cons:** The logic for space optimization can be less intuitive than the standard 2D DP approach.
### Explanation
A crucial observation transforms the problem: the characters that are part of the longest palindromic subsequence (LPS) of `s` already form a palindrome. We only need to add characters to mirror the ones not in the LPS. Thus, the number of insertions needed is `n - length(LPS)`. 

We can find the length of the LPS using dynamic programming. A standard 2D DP approach would take `O(n^2)` space. However, we can optimize this. When computing the LPS for a row `i`, we only need information from the previous row `i+1` and the current row `i`. This dependency allows us to use only a 1D array, `dp`, to store the values for the current row being computed, effectively reducing space complexity to `O(n)`.

```java
class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        // The problem is equivalent to finding the length of the Longest Palindromic Subsequence (LPS).
        // minInsertions = n - length(LPS).
        // We find length of LPS using space-optimized DP.
        
        int[] dp = new int[n];
        
        for (int i = n - 1; i >= 0; i--) {
            // Base case: LPS of a single character string is 1.
            dp[i] = 1;
            int prev = 0; // Stores dp[i+1][j-1]
            
            for (int j = i + 1; j < n; j++) {
                int temp = dp[j]; // Stores dp[i+1][j]
                if (s.charAt(i) == s.charAt(j)) {
                    dp[j] = 2 + prev;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
        
        int lpsLength = dp[n - 1];
        return n - lpsLength;
    }
}
```
### Algorithm
- Realize that `min_insertions = n - length(LPS)`, where LPS is the Longest Palindromic Subsequence.
- The problem is now to find the length of the LPS of `s`.
- Use a 1D array `dp[n]` to store the LPS lengths.
- Iterate `i` from `n-1` down to `0`. This corresponds to the row in a conceptual 2D DP table.
- For each `i`, iterate `j` from `i+1` to `n-1`.
- Use a `prev` variable to hold the value from the top-left diagonal cell (`lps(i+1, j-1)`).
- The recurrence for LPS length is:
  - If `s[i] == s[j]`, `lps(i, j) = 2 + lps(i+1, j-1)`.
  - If `s[i] != s[j]`, `lps(i, j) = max(lps(i+1, j), lps(i, j-1))`.
- After the loops, `dp[n-1]` will contain the LPS length of the whole string.
- Return `n - dp[n-1]`.

# Solutions
### Java

```java
class Solution {
private
  Integer[][] f;
private
  String s;
public
  int minInsertions(String s) {
    this.s = s;
    int n = s.length();
    f = new Integer[n][n];
    return dfs(0, n - 1);
  }
private
  int dfs(int i, int j) {
    if (i >= j) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int ans = 1 << 30;
    if (s.charAt(i) == s.charAt(j)) {
      ans = dfs(i + 1, j - 1);
    } else {
      ans = Math.min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
    }
    return f[i][j] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minInsertions(string s) {
    int n = s.size();
    int f[n][n];
    memset(f, -1, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (i >= j) {
        return 0;
      }
      if (f[i][j] != -1) {
        return f[i][j];
      }
      int ans = 1 << 30;
      if (s[i] == s[j]) {
        ans = dfs(i + 1, j - 1);
      } else {
        ans = min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
      }
      return f[i][j] = ans;
    };
    return dfs(0, n - 1);
  }
};

```

### Python

```python
class Solution:
    def minInsertions(self, s: str) -> int: @ cache def dfs(i: int, j: int) -> int: if i >= j: return 0 if s[i] == s[j]: return dfs(i + 1, j - 1) return 1 + min(dfs(i + 1, j), dfs(i, j - 1)) return dfs(0, len(s) - 1)

```