> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/minimum-insertions-to-form-a-palindrome.md).

# Minimum insertions to form a palindrome

Given a string **str**, the task is to find the minimum number of characters to be inserted to convert it to palindrome.

Before we go further, let us understand with few examples:

* **ab:** Number of insertions required is 1 i.e. **b**ab
* **aa:** Number of insertions required is 0 i.e. aa
* **abcd:** Number of insertions required is 3 i.e. **dcb**abcd
* **abcda:** Number of insertions required is 2 i.e. a**dc**bcda which is same as number of insertions in the substring bcd(Why?).
* **abcde:** Number of insertions required is 4 i.e. **edcb**abcde

```java
class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int dp[][] = new int[n][n];
        // Base case when i=j
        // then number of insertions = 0
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
                if (s.charAt(i) == s.charAt(j))
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
}
```