242. Minimum Insertion Steps to Make a String Palindrome

🔗 LeetCode Problem: 1312. Minimum Insertion Steps to Make a String Palindrome
📊 Difficulty: Hard
🏷️ Topics: Dynamic Programming, String, DP - Strings

Problem Statement

Given a string s, in one step you can insert any character at any position of the string.

Return the minimum number of steps to make s palindrome.

A palindrome is a string that reads the same backward as forward.

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already a palindrome so 0 insertions are needed.

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Constraints: - 1 <= s.length <= 500 - s consists of lowercase English letters only.

---

🧒 Understanding from Absolute First Principles

What Does "Insert to Make Palindrome" Mean?

Let's start with something simple:

Given: s = "ab"

Is "ab" a palindrome?
  Forward: "ab"
  Backward: "ba"
  Different! ✗

How to make it a palindrome by ONLY inserting?

Attempt 1: Insert 'b' at the start
  "bab" → Forward: "bab", Backward: "bab" ✓
  Palindrome! 1 insertion!

Attempt 2: Insert 'a' at the end
  "aba" → Forward: "aba", Backward: "aba" ✓
  Palindrome! 1 insertion!

Both work with 1 insertion!

KEY INSIGHT: We can ONLY insert, NOT delete or replace! 🔑

Why Is This Different from Other Problems?

COMPARISON:

Problem 238 (Longest Palindromic Subsequence):
  Find: What's already palindromic (by SKIPPING chars)
  Operation: Skip characters

This problem (Minimum Insertions):
  Make: The ENTIRE string palindromic (by ADDING chars)
  Operation: Insert characters

These seem OPPOSITE!

But wait... are they related? 🤔

Let me explore...

---

🤔 Building Intuition Through Examples

Example 1: Already a Palindrome

s = "aba"

Is it already a palindrome?
  Forward: "aba"
  Backward: "aba"
  Same! ✓

Insertions needed: 0 ✓

INSIGHT: If already palindrome, we're done! 🎯

Example 2: Simple Mismatch

s = "abc"

Not a palindrome!
  Forward: "abc"
  Backward: "cba"
  Different! ✗

How to fix?

Approach: Make it SYMMETRIC!

Option 1: Mirror the string
  "abc" → "abc" + reverse("ab") = "abcba"
  Insertions: 2 ('b' and 'a' at end)

Option 2: Think character by character
  'a' at start → need 'a' at end? 
  Wait, there's no 'a' at end in original!

Let me think differently...

Actually, let me trace what makes it palindrome:
  Original: a b c
  Target:   a b c b a
            ↑ ↑ ↑ ↑ ↑
            |     new
            original

I inserted 'b' and 'a' at the end!

Count: 2 insertions ✓

Can I do better than 2? Let me check...

What if I insert at the beginning?
  "abc" → "cbabc"
  Forward: "cbabc"
  Backward: "cbabc" ✓
  Insertions: 2 ('c' and 'b' at start)

Same count! Both are valid!

Example 3: Partial Palindrome

s = "mbadm"

Let me see what's already palindromic:

Reading forward: m b a d m
Reading backward: m d a b m

Notice: 'm' matches on both ends!

So the structure is:
  m [bad] m

The middle part "bad" needs work!

For "bad":
  Forward: "bad"
  Backward: "dab"

If I make "bad" into a palindrome:
  "bad" → "badab" (insert 'a', 'b')
  Or "bad" → "baddab" ? No, that's wrong...
  Or "bad" → "b a d a b" (insert 'a', 'b' symmetrically)

Actually, for "bad":
  Need: "badab" (2 insertions)
  Or: "dababad"? Too many...
  Or: "badabd" ? Is this palindrome?
      Forward: "badabd"
      Backward: "dbadab"
      No! ✗

Let me be systematic:
  "bad" → insert 'd' at start, 'b' at end → "dbadb"?
  No wait, that's 4 chars total, not palindrome

Hmm, I'm getting confused. Let me think of a SYSTEMATIC approach! 🤔

---

💡 The Key Insight - Connecting to What We Know

What If We Think in Reverse?

OBSERVATION:

To make a string palindrome by INSERTIONS:
  We need to ADD missing mirror characters

But what if I think of it differently?

ALTERNATIVE VIEW:

A palindrome is SYMMETRIC.
What if some characters are ALREADY in symmetric positions?

Example: s = "mbadm"
  m [bad] m
  ↑       ↑
  Already symmetric!

The characters that are ALREADY in correct palindromic positions
don't need any insertions!

EUREKA MOMENT:
  Characters already in palindromic subsequence → keep them!
  Characters NOT in palindromic subsequence → need mirrors!

This sounds like... LONGEST PALINDROMIC SUBSEQUENCE! 🎯

The Connection to LPS

HYPOTHESIS:

Minimum insertions = n - LPS

Where:
  n = length of string
  LPS = Longest Palindromic Subsequence length

Why would this work?

REASONING:

If LPS = k characters are already palindromic:
  These k characters are SYMMETRIC
  They don't need any insertions!

Remaining characters = n - k:
  These are NOT in the palindromic structure
  Each needs a MIRROR inserted!

Therefore: Insertions needed = n - LPS

Let me verify with examples!

Verification with Examples

Example 1: s = "aba"
  LPS = "aba" (entire string)
  LPS length = 3
  Insertions = 3 - 3 = 0 ✓
  Correct! Already palindrome!

Example 2: s = "abc"
  LPS = "a" or "b" or "c" (any single char)
  LPS length = 1
  Insertions = 3 - 1 = 2 ✓
  Correct! Need 2 insertions!

Example 3: s = "mbadm"
  LPS = "mam" or "mdm" (length 3)
  Let me check "mam": m_a__ m → yes! ✓
  LPS length = 3
  Insertions = 5 - 3 = 2 ✓
  Correct! Need 2 insertions!

The formula works! 🎉

But WHY does it work? Let me PROVE it!

---

🎯 Mathematical Proof of the Formula

Theorem: Minimum Insertions = n - LPS

THEOREM:
  The minimum number of insertions to make string s a palindrome
  equals len(s) - LPS(s)

PROOF:

Part 1: We CAN achieve n - LPS insertions
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Construction:
  Let P be the longest palindromic subsequence of s
  |P| = LPS

  Characters in s but NOT in P: n - LPS characters

  For each character c NOT in P:
    Find its symmetric position in final palindrome
    Insert a copy of c at that position

  Total insertions: n - LPS

  Claim: This creates a palindrome

  Proof of claim:
    - Characters in P are already symmetric (P is palindrome)
    - Each character not in P now has a mirror
    - All characters are now symmetric
    - Result is a palindrome ✓

  Therefore: We CAN do it in n - LPS insertions ✓

Part 2: We CANNOT do better than n - LPS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Proof by contradiction:
  Suppose we can make it palindrome with < n - LPS insertions

  Let k = number of insertions (k < n - LPS)
  Final palindrome has length n + k

  In a palindrome of length n + k:
    The palindromic subsequence has length at least n + k
    (the entire string is palindromic!)

  But this palindrome contains all n original characters
  So it has a palindromic subsequence of length at least:
    n - k (the original chars that stayed in palindromic positions)

  Wait, this is getting complex. Let me think more carefully...

  Alternative proof:

  In the final palindrome:
    Every character has a mirror
    (That's what makes it palindromic)

  Original string has n characters

  Characters that are ALREADY in palindromic positions: LPS
  These don't need mirrors inserted (they already have them)

  Characters NOT in palindromic positions: n - LPS
  These NEED mirrors inserted

  Minimum insertions = n - LPS

  We cannot do better because:
    Every non-palindromic character MUST have a mirror
    We must insert at least one character for each ✓

QED: Minimum insertions = n - LPS ✓

Why This Proof Matters

DEEPER UNDERSTANDING:

The proof reveals the STRUCTURE:

1. Some characters are already palindromic (LPS)
   → They're in symmetric positions
   → No work needed!

2. Remaining characters are not palindromic (n - LPS)
   → They lack symmetric partners
   → Must insert partners!

This is not just a formula to memorize!
It's a STRUCTURAL INSIGHT about palindromes! 🔑

---

🔴 Approach: Reduce to LPS Problem

The Strategy

ALGORITHM:

Step 1: Compute LPS(s)
  Use standard LPS algorithm (Problem 238)

Step 2: Calculate insertions
  insertions = len(s) - LPS(s)

Step 3: Return result

That's it! The problem REDUCES to LPS! 🎯

Why This Reduction Works

REDUCTIONS IN COMPUTER SCIENCE:

Problem A reduces to Problem B means:
  If we can solve B, we can solve A!

Here:
  "Minimum Insertions" reduces to "LPS"

Benefits:
  1. We already know how to solve LPS! ✓
  2. We reuse existing algorithm! ✓
  3. We get same time complexity! ✓
  4. We understand the CONNECTION! ✓

This is PROBLEM-SOLVING at a higher level! 🚀

---

🟢 Complete Implementation

Using LPS (Problem 238 Solution)

class Solution {
    public int minInsertions(String s) {
        int n = s.length();

        // Find longest palindromic subsequence
        int lps = longestPalindromeSubseq(s);

        // Minimum insertions = total length - LPS
        return n - lps;
    }

    // Standard LPS algorithm (from Problem 238)
    private int longestPalindromeSubseq(String s) {
        int n = s.length();

        // dp[i][j] = LPS length in s[i...j]
        int[][] dp = new int[n][n];

        // Base case: single characters
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // Fill for increasing substring lengths
        // Using index-based approach: i backward, j forward
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    // Characters match - both in palindrome
                    dp[i][j] = 2 + dp[i + 1][j - 1];
                } else {
                    // Characters don't match - skip one
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

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

Why Backward Loop for LPS?

REMINDER from Problem 238:

dp[i][j] for LPS needs:
  - dp[i+1][j-1] (larger i, larger j)
  - dp[i+1][j] (larger i)
  - dp[i][j-1] (larger j)

Dependencies point to LARGER indices!

Therefore:
  i must go BACKWARD: n-1 → 0
  j must go FORWARD: i+1 → n-1

This ensures dependencies are computed first! ✓

---

🔍 Detailed Example Walkthrough

Example: s = "mbadm"

Step 1: Compute LPS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

s = "mbadm", n = 5

Build LPS table:

        0   1   2   3   4
        m   b   a   d   m
    0 m 1   1   1   1   3
    1 b     1   1   1   1
    2 a         1   1   1
    3 d             1   1
    4 m                 1

(Filling details omitted - see Problem 238)

LPS = dp[0][4] = 3

The palindromic subsequence: "mam" or "mdm"
  "mbadm" → [m]ba[d][m] → "mdm" ✓
  "mbadm" → [m]b[a]d[m] → "mam" ✓

Step 2: Calculate insertions
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

insertions = n - LPS
           = 5 - 3
           = 2 ✓

Step 3: Verify
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Original: m b a d m
LPS:      m   a   m  (chars at positions 0, 2, 4)

Characters NOT in LPS: 'b' (pos 1), 'd' (pos 3)

To make palindrome:
  Insert mirror for 'b': need 'b' symmetrically
  Insert mirror for 'd': need 'd' symmetrically

One valid result:
  m b d a d b m
  ↑ ↑ ↑ ↑ ↑ ↑ ↑
  | | new | | |
  |--symmetric--|

Length: 7 = 5 + 2 ✓
Palindrome check:
  Forward:  "mbdadbm"
  Backward: "mbdadbm"
  Same! ✓

Alternative result:
  m d b a b d m

Both are valid palindromes with 2 insertions! ✓

---

🤔 Deep Understanding - Why Does This Work?

The Structural Insight

PALINDROME STRUCTURE:

A palindrome is SYMMETRIC around center:

Example: "racecar"
  r a c e c a r
  ↑     ↑     ↑
  |--mirror--|

Every character has a PARTNER at mirror position!

Now, given non-palindrome: "abc"
  a b c

Some characters might ALREADY have partners (LPS)
Some don't (need insertions)

For "abc":
  LPS = 1 (any single character, say 'a')
  'a' is "palindromic" by itself
  'b' and 'c' need partners!

Insert partners:
  a b c b a
  ↑ ↑ ↑ ↑ ↑
  |--symmetric--|

  'b' mirrors with 'b'
  'c' is center

2 insertions needed! ✓

Why LPS Gives the Answer

PROOF INTUITION:

LPS identifies: Characters already in palindromic positions

Key insight:
  If k characters are palindromic,
  they're ALREADY symmetric!

Remaining n - k characters:
  Not symmetric
  Need mirrors

Minimum mirrors needed = n - k = n - LPS

This is OPTIMAL because:
  We can't use fewer mirrors (some chars need partners)
  We don't need more mirrors (LPS are already good)

Perfect! ✓

---

🎯 Alternative Perspective: Direct DP

Can We Solve Without Reducing to LPS?

INTERESTING QUESTION:

Instead of:
  1. Compute LPS
  2. Calculate n - LPS

Can we directly compute minimum insertions?

Let me think...

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

Base cases:
  dp[i][i] = 0 (single character already palindrome)

Recurrence:

If s[i] == s[j]:
  Endpoints match!
  Make s[i+1...j-1] palindrome, and we're done!
  dp[i][j] = dp[i+1][j-1]

Else:
  Endpoints don't match
  Must insert mirror for one

  Option 1: Insert s[i] at end
            Make s[i+1...j] palindrome
            dp[i][j] = 1 + dp[i+1][j]

  Option 2: Insert s[j] at start
            Make s[i...j-1] palindrome
            dp[i][j] = 1 + dp[i][j-1]

  dp[i][j] = min(option 1, option 2)

This ALSO works! ✓

Comparing Both Approaches

APPROACH 1 (Reduce to LPS):
  Compute: LPS first
  Formula: n - LPS

  Pros: Reuses existing algorithm
        Clear conceptual connection
  Cons: Two-step process

APPROACH 2 (Direct DP):
  Compute: Insertions directly
  Recurrence: Based on endpoints

  Pros: One-step process
        Direct answer
  Cons: New DP to understand

WHICH IS BETTER?

For learning: Approach 1! (builds on knowledge)
For coding: Either! (same complexity)

Both have O(n²) time and space! ✓

Direct DP Implementation

class Solution {
    public int minInsertions(String s) {
        int n = s.length();

        // dp[i][j] = min insertions for s[i...j]
        int[][] dp = new int[n][n];

        // Base case: single chars already palindrome
        // (dp[i][i] = 0 by default)

        // Fill using index-based: i backward, j forward
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    // Endpoints match - no insertion for them
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    // Endpoints don't match - insert one
                    dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

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

Why This Recurrence Is Correct

PROOF:

Case 1: s[i] == s[j]
  Claim: dp[i][j] = dp[i+1][j-1]

  Proof:
    Endpoints already match!
    They form palindromic structure: s[i] [...] s[j]
    Just need to make middle palindromic
    No insertion needed for endpoints
    dp[i][j] = dp[i+1][j-1] ✓

Case 2: s[i] != s[j]
  Claim: dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])

  Proof:
    Endpoints don't match
    Must insert mirror for one

    Option 1: Insert s[j] at position i
      New string: s[j] s[i...j]
      First and last now match (both s[j])
      Need to make s[i...j-1] palindrome
      Total: 1 + dp[i][j-1]

    Option 2: Insert s[i] at position j+1
      New string: s[i...j] s[i]
      First and last now match (both s[i])
      Need to make s[i+1...j] palindrome
      Total: 1 + dp[i+1][j]

    Take minimum: dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]) ✓

QED: The direct DP is correct! ✓

---

📊 Complexity Analysis

Both Approaches

APPROACH 1 (LPS-based):
  Step 1: Compute LPS
    Time: O(n²)
    Space: O(n²)

  Step 2: Calculate n - LPS
    Time: O(1)
    Space: O(1)

  Total:
    Time: O(n²)
    Space: O(n²)

APPROACH 2 (Direct DP):
  Fill DP table:
    Two nested loops: O(n²)
    Each cell: O(1)

  Total:
    Time: O(n²)
    Space: O(n²)

SAME COMPLEXITY! ✓

Space optimization possible:
  Both can use O(n) space (rolling array)
  But loses ability to reconstruct solution

---

🎯 Pattern Recognition

This Problem's Family

PALINDROME + TRANSFORMATIONS:

Problem 238: Longest Palindromic Subsequence
  Find: What's already palindromic
  Operation: None (just find)

Problem 242: Minimum Insertions to Make Palindrome
  Find: How many chars to add
  Formula: n - LPS
  Operation: Insert

Related: Minimum Deletions to Make Palindrome
  Find: How many chars to remove
  Formula: n - LPS
  Operation: Delete

PATTERN:
  All connect to LPS!
  LPS is the CORE structure! 🔑

Template:
  1. Find LPS
  2. Use formula based on operation
  3. Insertions/Deletions = n - LPS

Why Insertions = Deletions

INTERESTING OBSERVATION:

Minimum insertions to make palindrome = n - LPS
Minimum deletions to make palindrome = n - LPS

SAME FORMULA! 🤔

Why?

Insertions:
  Keep LPS, insert mirrors for rest
  Total: LPS + (n - LPS) chars = n + (n - LPS) length
  Insertions: n - LPS

Deletions:
  Keep LPS, delete rest
  Total: LPS chars remain
  Deletions: n - LPS

Both identify the SAME set of characters:
  The n - LPS characters not in LPS!

One adds mirrors, one removes them!
Different operations, same count! ✓

---

💡 Key Insights Summary

The Core Understanding

1. WHY reduce to LPS?
   LPS identifies already-palindromic structure
   Remaining chars need mirrors

2. WHY is formula n - LPS?
   LPS chars are symmetric (don't need work)
   n - LPS chars need mirrors inserted

3. WHY two approaches work?
   Both identify same palindromic core
   Different ways to compute same structure

4. WHY backward loops?
   Dependencies on larger indices
   Must compute large → small

5. WHY is this a pattern?
   Many problems reduce to LPS
   Understanding LPS unlocks many problems

---

📝 Quick Revision

🎯 Core Formula

Minimum Insertions = n - LPS

Why? - LPS chars already palindromic - Remaining need mirrors - Each mirror = 1 insertion

⚡ Quick Implementation

public class Solution {
  public int minInsertions(String s) {
    int len = s.length();
    // Length of longest palindrome subsequence - same as earlier prob.
    // "mbadm" => LPS is "mbm" or "mam" or "mdm"
    // To make it palindrome, how many insertions? len - lps

    // int lps = recursive(s, 0, len - 1);

    // Integer[][] memo = new Integer[len + 1][len + 1];
    // int lps = topDown(s, 0, s.length() - 1, memo);

    int lps = bottomUp(s);

    return len - lps;
  }

  private int bottomUp(String s) {
    int len = s.length();
    int[][] dp = new int[len][len];

    for (int i = len - 1; i >= 0; i--) {
      dp[i][i] = 1; // always 1 in diagonal for a single char

      for (int j = i + 1; j < len; j++) {
        if (s.charAt(i) == s.charAt(j)) {
          // if chars match, shrink both ends
          dp[i][j] = 2;

          if (i + 1 < len) {
            dp[i][j] += dp[i + 1][j - 1];
          }
        } else {
          // if chars do not match, shrink one char at a time
          dp[i][j] = dp[i][j - 1];

          if (i + 1 < len) {
            dp[i][j] = Math.max(dp[i + 1][j], dp[i][j]);
          }
        }
      }
    }

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

  private int topDown(String s, int i, int j, Integer[][] memo) {
    if (i == j) {
      return 1;
    }

    if (i > j) {
      return 0;
    }

    if (memo[i][j] != null) {
      return memo[i][j];
    }

    if (s.charAt(i) == s.charAt(j)) {
      return 2 + topDown(s, i + 1, j - 1, memo);
    }

    return memo[i][j] = Math.max(topDown(s, i + 1, j, memo), topDown(s, i, j - 1, memo));
  }

  private int recursive(String s, int i, int j) {
    if (i == j) {
      return 1;
    }

    if (i > j) {
      return 0;
    }

    if (s.charAt(i) == s.charAt(j)) {
      return 2 + recursive(s, i + 1, j - 1);
    }

    return Math.max(recursive(s, i + 1, j), recursive(s, i, j - 1));
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.minInsertions("zzazz") == 0);
    System.out.println(s.minInsertions("mbadm") == 2);
    System.out.println(s.minInsertions("leetcode") == 5);
  }
}

🔑 Why It Works

• LPS approach: Reuses known algorithm
• Direct approach: Same structure, direct computation
• Both: O(n²) time and space

---

🎉 Congratulations!

You've mastered this through: - ✅ Discovering the LPS connection - ✅ Mathematical proof of formula - ✅ Understanding two valid approaches - ✅ Proving direct DP correctness - ✅ Pattern recognition (insertion = deletion count)

Deep understanding through reasoning! 🚀✨