Definition
- Key insight is that characters in the longest palindromic subsequence already have their mirror partners; only the remaining characters need mirrors inserted.
- LPS computation uses the range DP: matching ends add 2, mismatching ends take the max of dropping one end.
- Insertions equal
n - LPS, one mirror per unmatched character. - Equals minimum deletions because deleting an unmatched character and inserting its mirror are symmetric.
- O(n squared) time and space for the DP table.
The National Bank of India pads short reference codes into a symmetric canonical shape by adding the fewest characters so the code reads the same both ways. The fewest insertions equal the code length minus its longest symmetric core, because only the characters without a mirror partner need one inserted.
Understanding the Concepts
What is the problem?
Given a string, find the minimum number of characters to insert anywhere to make the entire string a palindrome. For "abcda", insert 'c' and 'b' to get "abcdcba", so the answer is 2.
package com.bank.dsa;
public class MinInsertionsPalindrome {
public static int minInsertions(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = 2 + dp[i + 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return n - dp[0][n - 1];
}
}
Why does this reduce to the LPS?
Characters that belong to the longest palindromic subsequence already have their symmetric partners within the string. They can stay in place. Every other character is unmatched and needs a mirror partner inserted on the other side. So the number of insertions equals the number of unmatched characters, which is n - LPS.
package com.bank.dsa;
public class InsertionReductionDemo {
public static void main(String[] args) {
String s = "ABCDA";
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j)
? 2 + dp[i + 1][j - 1]
: Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
int lps = dp[0][n - 1];
System.out.println("String: " + s);
System.out.println("LPS length: " + lps + " (e.g., 'ADA')");
System.out.println("Min insertions: " + (n - lps));
System.out.println("Result after insertion: ABCDCBA");
}
}
String: ABCDA
LPS length: 3 (e.g., 'ADA')
Min insertions: 2
Result after insertion: ABCDCBA
How does the LPS DP table work?
The entry dp[i][j] holds the length of the longest palindromic subsequence of the substring from i to j. When the characters at both ends match, they both belong to the palindrome, adding 2 to the inner answer. When they do not match, one end must be dropped, taking the max of dropping left or right.
package com.bank.dsa;
public class LPSTableDemo {
public static void main(String[] args) {
String s = "BACA";
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = 2 + dp[i + 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
System.out.println("dp[" + i + "][" + j + "]=" + dp[i][j]);
}
}
System.out.println("LPS: " + dp[0][n - 1]);
}
}
dp[2][3]=2
dp[1][2]=1
dp[1][3]=2
dp[0][1]=1
dp[0][2]=1
dp[0][3]=2
LPS: 2
Why does this equal minimum deletions?
Deleting an unmatched character and inserting its mirror on the other side are two symmetric ways to fix the same asymmetry. Both operations remove one unit of imbalance. So minimum deletions equals minimum insertions, and both are n - LPS.
package com.bank.dsa;
public class EqualsDeleteDemo {
public static void main(String[] args) {
String s = "ABCDA";
System.out.println("Min insertions: " + MinInsertionsPalindrome.minInsertions(s));
System.out.println("Min deletions: " + MinDeletionsPalindrome.minDeletions(s));
System.out.println("Both equal n - LPS");
}
}
Min insertions: 2
Min deletions: 2
Both equal n - LPS
What are the edge cases?
A palindrome needs 0 insertions. A single character needs 0. An empty string needs 0. A string with all distinct characters needs n-1 insertions.
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println(MinInsertionsPalindrome.minInsertions("ABA")); // 0
System.out.println(MinInsertionsPalindrome.minInsertions("A")); // 0
System.out.println(MinInsertionsPalindrome.minInsertions("ABCD")); // 3
}
}
0
0
3
What is the time and space complexity?
Time is O(n squared). Space is O(n squared) for the table, reducible to O(n) with a rolling array.
What are common mistakes?
Confusing insertions with deletions (they give the same number). Using the wrong DP (substring boolean table instead of subsequence integer table). Forgetting to subtract from n.
What are common interview follow-up questions?
- How would you reconstruct the actual palindrome after insertions?
- How does this relate to the edit distance problem?
- Can you solve this with the reverse-string LCS approach?
- What if insertions are only allowed at one end?
Visual Overview
String: "ABCDA" (n=5)
LPS = "ADA" (length 3)
Unmatched characters: B, C (2 characters)
Each needs a mirror inserted.
Original: A B C D A
LPS: A D A ← these stay
Insert: B' C' ← mirrors for B and C
Result: A B C D C' B' A
= "ABCDCBA" (palindrome)
Min insertions = n - LPS = 5 - 3 = 2
┌──────────────────────────────────────┐
│ Insertions = Deletions = n - LPS │
│ Both fix the same unmatched chars │
└──────────────────────────────────────┘
Key Takeaway
The Minimum Insertions to Form a Palindrome reduces to the Longest Palindromic Subsequence, just like the minimum deletions problem. Characters in the LPS already have their mirror partners and stay in place. Every character outside the LPS needs a mirror partner inserted, so the answer is n - LPS.
Rajesh at the National Bank of India uses this to pad short reference codes into a symmetric canonical shape for a fixed template. The LPS is computed with the standard range DP: matching ends add 2, mismatching ends take the max of dropping one end. The answer is read from the corner of the table.
The deep connection is that minimum insertions and minimum deletions give the same number for making a string palindrome. Deleting an unmatched character and inserting its mirror are two symmetric ways to fix the same asymmetry. Explaining this duality in an interview shows understanding of the pattern beyond mechanical DP construction.
The time and space are both O(n squared), reducible to O(n) space with a rolling array. A palindrome needs 0 insertions, and a string of all distinct characters needs n-1.
Remember one sentence: minimum insertions equals n minus the longest palindromic subsequence, because every unmatched character needs exactly one mirror partner inserted.
---