Definition
- Key insight is that the characters we keep must form a palindromic subsequence in their original order.
- Longest palindromic subsequence (LPS) is computed with a range DP table where matching ends add 2 and mismatching ends take the max of dropping one end.
- Deletions equal
n - LPS, the characters not part of the longest symmetric core. - Equals minimum insertions because deleting an unmatched character and inserting its mirror are symmetric fixes for the same imbalance.
- O(n squared) time and space for the DP table.
The National Bank of India wants to normalize legacy account tags into a symmetric canonical form by removing the fewest characters. The characters that stay must read the same both ways, forming the longest palindromic subsequence. Everything else gets deleted.
Understanding the Concepts
What is the problem?
Given a string, find the minimum number of character deletions to make it a palindrome. For "abcda", removing 'b' and 'c' leaves "ada" which is a palindrome, so the answer is 2.
package com.bank.dsa;
public class MinDeletionsPalindrome {
public static int minDeletions(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 longest palindromic subsequence?
The characters we choose to keep must form a palindrome while maintaining their original order. That is exactly the definition of a palindromic subsequence. To delete as few as possible, we keep as many as possible, which means keeping the longest palindromic subsequence. The deletions are everything left over.
package com.bank.dsa;
public class ReductionDemo {
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 + " (length " + n + ")");
System.out.println("Longest palindromic subsequence: " + lps);
System.out.println("Minimum deletions: " + (n - lps));
}
}
String: ABCDA (length 5)
Longest palindromic subsequence: 3
Minimum deletions: 2
How does the LPS recurrence work?
The entry dp[i][j] holds the longest palindromic subsequence of the substring from i to j. When the ends match, both characters are part of the palindrome, so add 2 to the inner answer. When they do not match, one end must be dropped, so take the max of dropping the left end or the right end.
package com.bank.dsa;
public class LPSRecurrenceDemo {
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];
System.out.println("dp[" + i + "][" + j + "]=" + dp[i][j] + " (match '" + s.charAt(i) + "')");
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
System.out.println("dp[" + i + "][" + j + "]=" + dp[i][j] + " (mismatch)");
}
}
}
System.out.println("LPS: " + dp[0][n - 1] + ", Deletions: " + (n - dp[0][n - 1]));
}
}
dp[2][3]=2 (match 'A')
dp[1][2]=1 (mismatch)
dp[1][3]=2 (mismatch)
dp[0][1]=1 (mismatch)
dp[0][2]=1 (mismatch)
dp[0][3]=2 (mismatch)
LPS: 2, Deletions: 2
Why does this also equal the minimum insertions?
Deleting an unmatched character and inserting its mirror on the other side are two symmetric ways to fix the same imbalance. Both operations reduce the problem by one unmatched character. So the minimum deletions to make a palindrome equals the minimum insertions to make a palindrome. Both are n - LPS.
package com.bank.dsa;
public class DeletionsEqualsInsertions {
public static void main(String[] args) {
String s = "ABCDA";
int deletions = MinDeletionsPalindrome.minDeletions(s);
// Minimum insertions would also be 2
System.out.println("Min deletions: " + deletions);
System.out.println("Min insertions: " + deletions + " (same value)");
}
}
Min deletions: 2
Min insertions: 2 (same value)
What is the time and space complexity?
Time is O(n squared) for filling the n-by-n table. Space is O(n squared) for the table. Space can be reduced to O(n) with a rolling two-row array since each row only depends on the row below it.
What are the edge cases?
A string that is already a palindrome needs 0 deletions. A single character needs 0 deletions. An empty string needs 0 deletions. A string with all distinct characters needs n-1 deletions (keep any one character).
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println(MinDeletionsPalindrome.minDeletions("ABA")); // 0
System.out.println(MinDeletionsPalindrome.minDeletions("A")); // 0
System.out.println(MinDeletionsPalindrome.minDeletions("ABCD")); // 3
}
}
0
0
3
What are common mistakes?
Confusing this with the minimum deletions to make two strings equal (which uses LCS, not LPS). Using the substring palindrome DP (boolean table) instead of the subsequence DP (integer table). Forgetting to subtract from n at the end.
What are common interview follow-up questions?
- How would you reconstruct which characters to delete?
- How does this compare to the edit distance problem?
- Can you optimize space to O(n) with a rolling array?
- What if you can delete from only one end of the string?
Visual Overview
String: "ABCDA" (n=5)
┌──────────────────────────────────────────┐
│ Longest Palindromic Subsequence (LPS) │
│ │
│ Match: dp[i][j] = 2 + dp[i+1][j-1] │
│ Mismatch: dp[i][j] = max(dp[i+1][j], │
│ dp[i][j-1]) │
└──────────────────────────────────────────┘
LPS of "ABCDA":
A matches A (positions 0,4) ── LPS includes both
Inner "BCD" has LPS = 1 (any single char)
Total LPS = 2 + 1 = 3 ("ADA" or "ACA")
Deletions = n - LPS = 5 - 3 = 2
┌───────────┐ ┌───────────┐
│ A B C D A │ ──→ │ A _ _ D A │ ──→ "ADA"
│ keep keep│ │ delete B,C│
└───────────┘ └───────────┘
Key Takeaway
The Minimum Deletions to Make a Palindrome reduces cleanly to the Longest Palindromic Subsequence. The characters you choose to keep must already form a palindrome in their original order, which is exactly a palindromic subsequence. To delete as few as possible, keep the longest palindromic subsequence and the answer is simply n - LPS.
Rajesh at the National Bank of India uses this during data migration to normalize legacy account tags into a symmetric canonical form with the fewest character removals. The LPS is computed with the standard two-ended range table: matching ends add 2 to the inner answer, mismatching ends take the max of dropping one end. The final answer is read from the corner.
A point worth making in an interview is that this same number equals the minimum insertions to make a palindrome. Deleting an unmatched character and inserting its mirror are symmetric operations that fix the same imbalance. Both reduce to the same LPS quantity. This shows deep understanding of the pattern.
The time and space complexity are both O(n squared). Space can be reduced to O(n) with a rolling two-row array since each row only depends on the previous row.
Remember one sentence: minimum deletions equals string length minus the longest palindromic subsequence length, because the kept characters must form the longest possible symmetric core.
---