Minimum Insertions to Make String Palindrome

Intuition

At first glance, it seems like we need to decide where to insert characters to make the string a palindrome.

Instead of thinking about what to insert, think about what we can keep.

The characters that are already part of the Longest Palindromic Subsequence (LPS) do not need any insertion.

Only the remaining characters need to be inserted.

For example,

String

abcda

The Longest Palindromic Subsequence is

aca

Length = 3

Characters not in LPS

b
d

These are the characters we need to insert.

Hence,

Minimum Insertions = Length of String - Length of LPS

Now the problem becomes finding the Longest Palindromic Subsequence (LPS).

Even better,

The Longest Palindromic Subsequence is simply the Longest Common Subsequence (LCS) between the string and its reverse.

Example

Original

abcda

Reverse

adcba

LCS

aca

Length = 3

Answer

5 - 3 = 2

Brute Force Approach

Try every possible insertion recursively.

At every mismatch,

• Insert the left character on the right.
• Insert the right character on the left.

Take the minimum of both possibilities.

Example

abc

↓

Insert 'a'

↓

Insert 'b'

↓

Insert 'c'

Since every mismatch creates two recursive choices, the number of possibilities grows exponentially.

Complexity

• Time: O(2^N)
• Space: O(N) (Recursion Stack)

Optimal Approach (Dynamic Programming)

Observation

Minimum Insertions

=

Length of String

-

Longest Palindromic Subsequence

And,

Longest Palindromic Subsequence

=

Longest Common Subsequence

(String, Reverse(String))

Algorithm

1. Reverse the string.
2. Find the Longest Common Subsequence (LCS) between the original string and the reversed string.
3. Return:

Length - LCS

Example

String

mbadm

Reverse

mdabm

LCS

mam

Length

3

Answer

5 - 3 = 2

Java Code

public int minInsertions(String s) {

    String rev = new StringBuilder(s).reverse().toString();

    int n = s.length();
    int[][] dp = new int[n + 1][n + 1];

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= n; j++) {

            if (s.charAt(i - 1) == rev.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return n - dp[n][n];
}

Complexity

• Time: O(N²)
• Space: O(N²)

Interview One-Liner: Convert the problem into finding the Longest Palindromic Subsequence, which can be computed as the Longest Common Subsequence between the string and its reverse.