**2**, and the resulting palindrome is “cabbac”

**two**characters at a minimum to make it a palindrome “abcba”

**0**.

**Case 1**:The first and last characters are equal. In this case, the minimum number of characters to insert depends on the sub-string between the first and last characters.- For example consider the string “abca”, the value depends on the sub-string “bc”

**case 2**:The first and last characters are not equal. In this case, we have to make the first and last characters equal to make it a palindrome. We can do this in two ways. Either we can insert a new character before the first character, or next to the last character.- For example consider “gcc”, to make first and last characters equal, we can insert a “c” first or insert a “g” last. It either becomes “cgcc” or “gccg”. since “gccg” is minimal way of making a palindrome, We just need to insert
**1**character.

**MCI**. It can be defined as follows. str is a string of length n.

**MCI(str)** = **MCI( str[1:n-2] )** if str[0] = str[n-1]

= **Min( MCI(str[0:n-2]), MCI(str[1:n-1]))+1** otherwise

A naive recursive implementation is straight forward. To implement dynamic programming solution, we create a a two dimensional table of size n*n.

table[i][j] indicates MCI of the sub-string str[i:j] the table is calculated using the following rules.

table[i][i] is always 0 because a single character is a palindrome.

**table[i][j] = table[i+1][j-1]** if str[i] = str[j]

**= Min(table[i+1][j], table[i,j-1])+1** otherwise

We construct this table in bottom up manner i.e solve the smaller problems first and use their result to solve bigger problems. Finally table[0][n-1] contains the required value.

Below is the dynamic programming implementation in C++.