Minimum Insertion Steps to Make a String Palindrome

A word, phrase, or sequence that reads the same backwards as forwards is a palindrome. For example the sequence "Step on no pets" is a palindrome. Today, let's focus on converting a sequence into a palindrome by inserting characters at arbitrary positions in the original input sequence.

Minimum Insertion Steps to Make a String Palindrome - Problem Statement

Given an input sequence $s$, in one step you can insert any character at any position of the input sequence. Return the minimum number of steps to make $s$ palindrome. For example, given the input sequence "leetcode", inserting five characters the string becomes "leetcodocteel". This is the minimum number of insertions required to make the input sequence a palindrome.

Minimum Insertion Steps to Make a String Palindrome - Definition

Let $s$ be an input sequence, $i$ and $j$ denote the start and end positions of a subsequence. Let $p[i][j]$ be the minimum number of insertions required to make subsequence $s_i \ldots s_j$ palindrome. Here's our recurrence for the longest palindrome subsequence problem.

$$p[i][j] =
\begin{cases}
p[i + 1][j - 1] + 2,  & \text{if $x_i == x_j$} \\[2ex]
max(p[i][j - 1], l[i + 1][j]), & \text{otherwise.}
\end{cases}$$

Minimum Insertion Steps to Make a String Palindrome - Approach

If you look at the problem carefully, due to the symmetry of the palindrome sequence, the minimum number of insertions required to make a string palindrome is equal to the minimum number of deletions required to make it a palindrome. Thus let $I(s)$ be the minimum number of insertions required to make $s$ palindrome and $D(s)$ be the minimum number of deletions required to make $s$ palindrome. We may then conclude that: 

$I(s) = D(s)$       $1.1$

by definition of the palindrome. If we can find the length of the longest palindrome subsequence of $s$, and deduct it from the length of the original sequence $s$, that gives us the answer according to the above theorem $1.1$ which we have derived. Here's our dynamic programming [1] algorithm to the longest palindrome subsequence problem.

**Input:** Input sequence $s$    
**Output:** Minimum number of insertions to make $s$ palindrome.  
MIN-PALINDROME-INSERTIONS(s)  
$\phantom{{}++{}}$ $n \gets s.length$  
$\phantom{{}++{}}$ let $p$ be $n \times n$ table   
$\phantom{{}++{}}$ `for` $i = 1$ to $n$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $p[i][i] \gets 1$  
$\phantom{{}++{}}$ `for` $j = 1$ to $n - 1$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $s_j == s_{j + 1}$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $p[j][j + 1] \gets 2$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `else`  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $p[j][j + 1] \gets 1$  
$\phantom{{}++{}}$ `for` $l = 3$ to $n$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `for` $i = 1$ to $n - l + 1$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $j \gets i + l - 1$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $s_i == s_j$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $p[i][j] \gets p[i + 1][j - 1] + 2$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `else`  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $p[i][j] \gets max(p[i][j - 1], p[i + 1][j])$  
$\phantom{{}++{}}$ `return`  $n - p[1][n]$  

Figure 1 shows the table $p$ computed by procedure $MIN-PALINDROME-INSERTIONS$ on the input sequence $s = $ leetcode. The $p$ table is rotated so that the main diagonal runs horizontally. The table uses only the main diagonal and upper triangle.

Sample Implementation

Here’s the sample implementation of algorithms described above along with a driver program. Make sure you pass the -ea JVM argument when you run the program to enable assertions.

Analysis

Let $n$ be the length of the input sequence. Our approach creates an $n \times n$ table, and the time that it takes to calculate the value of each table entry is $O(1)$. Thus, our approach involves $O(n^2)$ asymptotic time and space complexity.

References

[1] https://www.amazon.com/Introduction-Algorithms-fourth-Thomas-Cormen/dp/026204630X