Minimum Insertions to Make String Palindrome

Medium20–25 min

Topics

Dynamic ProgrammingString

Companies

AmazonGoogleAdobe

Given a string `s`, find the minimum number of characters that must be inserted (anywhere in the string) so the result reads the same forwards and backwards. The trick is to stop thinking about insertions directly and instead ask which characters of `s` are already "safe" — already part of some palindrome hiding inside the string. Any subsequence of `s` that's already a palindrome doesn't need help; everything else eventually needs a mirrored partner planted somewhere to balance it out. So the fewest possible insertions is exactly the length of `s` minus the length of its longest palindromic subsequence: keep that subsequence as the palindrome's "skeleton," and every character left over is one insertion. Finding that longest palindromic subsequence is itself a classic two-pointer interval problem — shrink the string from both ends, matching or dropping a side at each step, and cache the result per interval so it's computed once.

Test Case 1:

Input:s = "zzazz"

Output:0

Explanation:"zzazz" already reads the same forwards and backwards, so zero insertions are needed.

Test Case 2:

Input:s = "mbadm"

Output:2

Explanation:The longest palindromic subsequence hiding inside "mbadm" is "mdm" (length 3, keeping positions m-d-m) — the other 2 letters (b and a) each need a mirrored partner inserted, so 5 - 3 = 2.

Test Case 3:

Input:s = "g"

Output:0

Explanation:A single character is trivially its own palindrome — nothing to insert.

Constraints

◆0 ≤ s.length ≤ 12
◆s consists of lowercase English letters

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Longest Palindromic Subsequence

Brute

Every character that isn't part of some palindromic subsequence of s is a character that will eventually need a mirrored twin inserted somewhere in the string. So the fewest insertions possible is exactly s.length() minus the length of s's longest palindromic subsequence — keep that subsequence untouched, and insert a matching partner for every leftover character. Finding that subsequence length recursively is simple: given a window [i, j], if the two ends match, both belong to the subsequence and the middle window [i+1, j-1] is solved the same way, contributing 2 more; if they don't match, drop whichever end doesn't help and keep the better of the two smaller windows. With no memoization, the same window gets re-solved from scratch every time a different sequence of drops lands on it, so the call count grows exponentially with the string length.

TimeO(2ⁿ)

SpaceO(n)

Java

Try it out

class Solution {
    private String s;
    public int minInsertions(String s) {
        this.s = s;
        int n = s.length();
        if (n == 0) return 0;
        return n - solve(0, n - 1);
    }
    private int solve(int i, int j) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (s.charAt(i) == s.charAt(j)) {
            return 2 + solve(i + 1, j - 1);
        }
        return Math.max(solve(i + 1, j), solve(i, j - 1));
    }
}

Optimal — Bottom-Up Interval DP

Optimal

Build the longest-palindromic-subsequence table bottom-up instead of re-deriving each window from scratch. dp[i][j] holds the longest palindromic subsequence length within s[i..j]. Every single character is a palindrome of length 1, so the diagonal starts there. Then grow outward by window length: if the two ends of a window match, dp[i][j] is 2 plus whatever the inner window already computed (or exactly 2 for a length-2 window); otherwise dp[i][j] takes the better of dropping the left end or the right end, both already sitting in the table from a shorter window. Once dp[0][n-1] is known, the answer falls straight out of the same formula as the brute force: n minus that length.

TimeO(n²)

SpaceO(n²)