DP 29. Minimum Insertions to Make String Palindrome

This chapter explores how to find the minimum number of insertions required to transform any given arbitrary string into a palindrome. Building directly upon the Longest Common Subsequence (LCS) and Longest Palindromic Subsequence (LPS) foundations, this lesson provides an elegant mathematical reduction that simplifies a seemingly complex string-mutation problem into a simple subtraction.

1. Problem Statement & The Naive Upper Bound

Given any arbitrary string, the primary objective is to find the minimum number of character insertions needed to make it a palindrome.

Before minimizing, let's examine the worst-case scenario: Can we always make any string a palindrome?

• Yes. If you take any string and append its exact reverse to itself, the resulting string is guaranteed to be a palindrome.
• Example: For a string like abcda, the maximum number of insertions required is simply the length of the string ($N$). By taking abcda and appending its reverse adcba, you get abcdaadcba, which is a valid palindrome.

However, appending the entire reverse string is inefficient because it introduces redundant operations. The core question is: What is the absolute minimum number of insertions required?

2. Real-Life Analogy: Preserving the Core Structure

Real-Life Analogy: The Archway and Scaffold

Imagine building a stone archway. If you want to use the fewest new stones (insertions) to fix a crumbling, asymmetrical wall into a symmetric arch, you wouldn't tear down the parts that are already balanced. Instead, you identify the strongest symmetric core (the longest palindromic center), leave it completely untouched, and only forge mirror-image replacement stones for the missing sections on either side.

Applying this to strings:

1. If a portion of the string is already a palindrome, keep it intact.
2. Identify characters outside of this palindromic core that lack matching counterparts.
3. Mirror and insert only the missing counterparts.

3. Step-by-Step Exploration with Examples

Example 1: abcaa

• Let's test different palindromic portions we could keep intact:
  • Single character: a
  • Double character: aa
  • Longer sequence: aa or a
• If we keep the longest palindromic portion intact—such as aa at the end or a elements—we can minimize our work.
• Alternatively, consider a clearer example: abcaa. The longest palindromic subsequence is aa (or aba). If we keep aba intact, the remaining characters need matching.
• Let's take another explicit example taught in the lecture: abcda (or abc 🪞 aa).
  • If we want a palindrome, we can keep the longest palindromic subsequence intact.
  • For abcaa, the longest palindromic substring/subsequence is aa (or a...a).
  • By keeping the longest palindromic subsequence intact and inserting missing characters (like adding a matching a and b), we achieve a palindrome with the fewest operations.

Example 2: codingninjas

• Let's analyze the string codingninjas.
• Which portion forms the Longest Palindromic Subsequence (LPS)?
  • The subsequence i n g n i exists within codingninjas.
• Characters not part of this palindromic core:
  • Leftover prefix: codi
  • Leftover suffix: njas (excluding the LPS characters)
• To make the entire string a palindrome while keeping ingni fixed in the center:
  • We take the unmatched prefix codi, reverse it, and mirror it.
  • We take the unmatched suffix njas, reverse it, and mirror it.
• Conclusion: The characters belonging to the Longest Palindromic Subsequence remain untouched in their positions. Every other character outside this core requires a matching insertion.

4. The Core Mathematical Insight & Formula

Because the characters belonging to the Longest Palindromic Subsequence (LPS) are already positioned in a palindromic order, they require zero insertions. Every single character not part of the LPS must be mirrored by inserting its counterpart elsewhere in the string.

Why does this work?

1. Total characters in string = $N$
2. Characters already satisfying palindrome property = $\text{LPS}$
3. Characters requiring a mirrored partner = $N - \text{LPS}$

Thus, the problem of "Minimum Insertions to Make String Palindrome" is perfectly and directly reduced to finding the Longest Palindromic Subsequence (LPS).

5. Algorithmic Implementation

To solve this, we compute the LPS using Dynamic Programming (which is itself solved by finding the Longest Common Subsequence between the string and its reverse). Then, we apply our formula.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Helper function to find Longest Common Subsequence (LCS)
    int lcs(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1[i - 1] == text2[j - 1])
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }
    
    // Helper function to find Longest Palindromic Subsequence
    int longestPalindromeSubseq(string s) {
        string t = s;
        reverse(t.begin(), t.end());
        return lcs(s, t);
    }

public:
    int minInsertions(string s) {
        int n = s.size();
        int lpsLength = longestPalindromeSubseq(s);
        
        // Minimum insertions = Total Length - LPS Length
        return n - lpsLength;
    }
};

int main() {
    Solution sol;
    string s = "abcaa";
    cout << "Minimum Insertions: " << sol.minInsertions(s) << endl;
    return 0;
}

6. Execution Flow Walkthrough

Let's trace minInsertions("abcaa"):

7. Summary and Key Takeaways

• Reduction Principle: Problems asking for the minimum insertions to make a string a palindrome can always be solved by finding the Longest Palindromic Subsequence (LPS).
• The Core Formula: $\text{Minimum Insertions} = \text{Length of String } (N) - \text{LPS}(s)$.
• Preserve the Core: Characters within the LPS stay untouched; all remaining unmatched characters dictate the exact number of mirror insertions required.
• LPS via LCS: The Longest Palindromic Subsequence of a string $S$ is equivalent to the Longest Common Subsequence between $S$ and $\text{reverse}(S)$.
• Space Optimization: While standard DP tabulation uses an $O(N^2)$ 2D matrix, space can be optimized to $O(N)$ by keeping track of only the previous and current rows during the LCS computation.