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
- Reverse the string.
- Find the Longest Common Subsequence (LCS) between the original string and the reversed string.
- 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.