Dolly Sharma

Posted on Mar 22

📘 Minimum Insertions to Make a String Palindrome

#algorithms #computerscience #cpp #coding

🔹 Key Idea (MOST IMPORTANT)

👉 Use Longest Palindromic Subsequence (LPS)

Minimum Insertions = n - LPS

🔹 Why this works?

LPS = longest part already palindrome
Remaining characters must be inserted to fix symmetry

👉 So:

Total characters − already palindrome part = insertions needed

🔹 Convert to LCS

LPS(s) = LCS(s, reverse(s))

🔥 Final Formula

Min Insertions = n - LCS(s, reverse(s))

🔹 Example

s = "abcaa"

Reverse:

"aacba"

👉 LCS = "aca" → length = 3

Min Insertions = 5 - 3 = 2

🔹 Code (C++)

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.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(s1[i-1] == s2[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];
}

int minInsertions(string s) {
    string t = s;
    reverse(t.begin(), t.end());

    int lps = lcs(s, t);
    return s.size() - lps;
}

🔹 Space Optimized 🚀

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<int> prev(m+1, 0), curr(m+1, 0);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1])
                curr[j] = 1 + prev[j-1];
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        prev = curr;
    }
    return prev[m];
}

🔹 Alternative DP (Direct without LCS)

👉 Define:

dp[i][j] = min insertions to make s[i..j] palindrome

Transition:

If match:

dp[i][j] = dp[i+1][j-1]

If not:

dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])

🔹 Code (Direct DP)

int minInsertions(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for(int len = 2; len <= n; len++){
        for(int i = 0; i + len - 1 < n; i++){
            int j = i + len - 1;

            if(s[i] == s[j])
                dp[i][j] = dp[i+1][j-1];
            else
                dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]);
        }
    }

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

🔹 Complexity

Approach	Time	Space
LCS-based	O(n²)	O(n²) / O(n)
Direct DP	O(n²)	O(n²)

🧠 Key Pattern

👉 Whenever you see:

“Make palindrome”
“Minimum insert/delete”

➡️ Think:

Use LPS (LCS with reverse)

🔥 Interview Tip

If asked:

“Minimum insertions to make palindrome?”

👉 Answer:

“We compute LPS using LCS with reverse string, then subtract from length.”

⚡ Summary

Convert → LPS
LPS → LCS(s, reverse(s))
Answer → n - LPS

📘 Best Optimized Approach

(From Dynamic Programming)

🔹 Final Optimized Idea

We use:

Min Insertions = n - LCS(s, reverse(s))

👉 Optimize LCS to O(n) space

🔥 Fully Optimized Code (O(n²) time, O(n) space)

int minInsertions(string s) {
    int n = s.size();

    string t = s;
    reverse(t.begin(), t.end());

    vector<int> prev(n+1, 0), curr(n+1, 0);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(s[i-1] == t[j-1])
                curr[j] = 1 + prev[j-1];
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        prev = curr;
    }

    int lps = prev[n];
    return n - lps;
}

🔹 Space Complexity

Approach	Space
Normal DP	O(n²)
Optimized (above)	✅ O(n)

🔥 Can we optimize more?

👉 ❌ NO (for general case)

Why?

You must compare all pairs → needs O(n²) time
LCS inherently requires quadratic time

🔹 Alternative (Direct DP optimized?)

👉 Direct DP:

dp[i][j] = min insertions

❌ Cannot reduce to O(n) easily
👉 Because it depends on:

dp[i+1][j]
dp[i][j-1]
dp[i+1][j-1]

🧠 Final Takeaway

👉 Best you can do:

Metric	Optimal
Time	O(n²)
Space	✅ O(n)

⚡ Interview Answer (Perfect 🔥)