# Minimum Insertion Steps to Make a String Palindrome

### **Problem Statement:-**

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.

**Link:** [https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/](https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/)

### **Problem Explanation with examples:-**

**Example 1**

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

**Example 2**

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

**Example 3**

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

**Constraints**

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

### Intuition:-

* We are allowed to insert any number of characters at any position.
    
* So, if we find the longest palindromic subsequence, we can be sure about how many characters are already making up the palindrome part.
    
* The remaining characters need to be inserted to make the whole string a palindrome.
    
* The number of characters to be inserted is the difference between the length of the string and the length of the longest palindromic subsequence.
    
* To find the longest palindromic subsequence, we can use the longest common subsequence algorithm with the string and its reverse.
    

### Solution:-

* Define a function lcs(s1, s2, idx1, idx2) to find the longest common subsequence of s1 and s2.
    
* If idx1 &lt; 0 or idx2 &lt; 0, return 0.
    
* If s1\[idx1\] == s2\[idx2\], return 1 + lcs(s1, s2, idx1 - 1, idx2 - 1).
    
* Else, return max(lcs(s1, s2, idx1 - 1, idx2), lcs(s1, s2, idx1, idx2 - 1)).
    
* Define a function longestPalindromeSubseq(s) to find the longest palindromic subsequence of s.
    
* Return lcs(s, s\[::-1\], len(s) - 1, len(s) - 1) where s\[::-1\] is the reverse of s.
    
* Finally our answer is len(s) - longestPalindromeSubseq(s) where s is the input string.
    

### Code:-

JAVA Solution

```java
class Solution {
    public int minInsertions(String s) {
        return s.length() - longestPalindromeSubseq(s);
    }

    public int longestPalindromeSubseq(String s) {
        Integer[][][] dp = new Integer[s.length()][s.length()][2];
        return lcs(s, new StringBuilder(s).reverse().toString(), s.length() - 1, s.length() - 1, dp);
    }

    public int lcs(String s1, String s2, int idx1, int idx2, Integer[][][] dp) {
        if (idx1 < 0 || idx2 < 0) {
            return 0;
        }

        if (dp[idx1][idx2][0] != null) {
            return dp[idx1][idx2][0];
        }

        if (s1.charAt(idx1) == s2.charAt(idx2)) {
            dp[idx1][idx2][0] = 1 + lcs(s1, s2, idx1 - 1, idx2 - 1, dp);
        } else {
            dp[idx1][idx2][0] = Math.max(lcs(s1, s2, idx1 - 1, idx2, dp), lcs(s1, s2, idx1, idx2 - 1, dp));
        }

        return dp[idx1][idx2][0];
    }
}
```

Python Solution

```python
class Solution:
    def minInsertions(self, s: str) -> int:

        @cache
        def lcs(s1, s2, idx1, idx2):
            if idx1<0 or idx2<0:
                return 0
            
            if s1[idx1] == s2[idx2]:
                return 1 + lcs(s1, s2, idx1-1, idx2-1)
            
            return max(lcs(s1, s2, idx1-1, idx2), lcs(s1, s2, idx1, idx2-1))

        def longestPalindromeSubseq(s: str) -> int:
            return lcs(s, s[::-1], len(s)-1, len(s)-1)

        return len(s) - longestPalindromeSubseq(s)
```

### Complexity Analysis:-

**TIME**:-

The time complexity of the code is **O(n^2)** where n is the length of the input string as we are using the longest common subsequence algorithm to find the longest palindromic subsequence.

**SPACE**:-

The space complexity of the code is **O(n^2)** where n is the length of the input string as we are using a 2D dp array to store the results of the longest common subsequence algorithm.

### References:-

* [**DP**](https://www.geeksforgeeks.org/dynamic-programming/)
    
* [**LCS**](https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/)
    

### Connect with me:-

* [**Twitter**](https://twitter.com/lakshit_cs)
    
* [**Github**](https://github.com/Lakshit-Chiranjiv)
    
* [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)