Topics › Strings › Hard String Problems

Minimum insertions to make string palindrome

Hard TUF ID 312 SDE

Problem

Given a string s, you may insert characters only at the beginning of it. Return the minimum number of characters you must insert so that the result is a palindrome.

A note on which problem this is. In Striver’s SDE sheet this entry sits in String Part-II, right after the KMP / LPS array problem, and is stated as “minimum characters needed to be inserted in the beginning to make it palindromic”. That is the version solved here. If insertions are allowed anywhere in the string, the problem becomes a dynamic programme on intervals; that version is covered in Minimum insertions to make string palindrome - DP-29. LeetCode 214 (Shortest Palindrome) is the front-only version that returns the resulting string instead of the count.

Constraints: 0 ≤ n ≤ 10^5, s consists of letters. The KMP approach uses '$' as a separator, so s must not contain '$'.

Example 1

s = "abc"
answer = 2          // insert "cb" in front: "cbabc"

Example 2

s = "aacecaaa"
answer = 1          // insert "a" in front: "aaacecaaa"

Example 3

s = "abb"
answer = 2          // "bbabb"; with insertions anywhere one would suffice ("abba")

The reduction: keep the longest palindromic prefix

Suppose we insert a string X of length k in front and X + s is a palindrome. A palindrome equals its own reverse, so the first k characters of X + s must be the reverse of its last k characters, which are the last k characters of s. That fixes X completely. Now look at what is left in the middle: the first n - k characters of s sit between X and its mirror image, so they must read the same in both directions. In other words, inserting k characters works exactly when s[0..n-k) is a palindrome.

To insert as few as possible, keep the longest prefix of s that is already a palindrome and mirror everything after it:

answer = n - (length of the longest palindromic prefix of s)

For "aacecaaa" the longest palindromic prefix is "aacecaa" (length 7), so the answer is 8 - 7 = 1. A single character is always a palindrome, so the answer is at most n - 1 for a non-empty string. All three approaches below are different ways of finding that prefix length.

Approach 1: Brute force

Intuition. Try prefix lengths from the longest (n) down to 1, and stop at the first prefix that is a palindrome. Checking one prefix is a two-pointer scan from both ends.

Algorithm.

For k = n down to 1: if s[0..k) is a palindrome, return n - k.
Return 0 (only reached for the empty string).

static int bruteForce(String s) {
    int n = s.length();
    for (int k = n; k > 0; k--) {
        if (isPalindrome(s, 0, k - 1)) return n - k;   // keep s[0..k), mirror the other n - k characters in front
    }
    return 0;                                          // only reached when s is empty
}

static boolean isPalindrome(String s, int lo, int hi) {
    while (lo < hi) {
        if (s.charAt(lo++) != s.charAt(hi--)) return false;
    }
    return true;
}

Complexity. Time O(n^2): up to n prefixes, each checked in O(n). Space O(1).

The worst case is a string like "aaaabaaa", with one fewer a after the b than before it. Every prefix that contains the b matches many as from both ends before the b meets an a, and only the all-a prefix succeeds. That costs about n^2/8 comparisons, over a billion for n = 10^5.

Approach 2: Better, rolling hashes

Intuition. A prefix is a palindrome when it equals its own reverse. If we can maintain a hash of the prefix and a hash of its reverse while the prefix grows one character at a time, each palindrome test becomes a comparison of two numbers.

With a base B and a modulus M, define for the prefix s[0..i]:

the forward hash F = s[0]·B^i + s[1]·B^(i-1) + ... + s[i]·B^0, which is the usual polynomial hash of the prefix read left to right;
the reverse hash R = s[0]·B^0 + s[1]·B^1 + ... + s[i]·B^i, which is the same polynomial hash of the prefix read right to left.

Both extend in O(1) when s[i] arrives: F = F·B + s[i] shifts all old terms up one power, and R = R + s[i]·B^i puts the new character on top. If the prefix is a palindrome, the two strings are identical, so F == R. The converse holds unless two different strings collide modulo M; using two independent primes makes that so unlikely (around 10^-18 per test) that it is ignored in practice, which is also how Rabin Karp is used.

Algorithm.

Keep F and R for two moduli, plus the current power B^i for each.
For each i, update all four hashes and both powers.
If both hash pairs agree, record best = i + 1.
Return n - best.

static int rollingHash(String s) {
    final long B = 131, M1 = 1_000_000_007L, M2 = 998_244_353L;   // base and two prime moduli
    long fwd1 = 0, fwd2 = 0, rev1 = 0, rev2 = 0, pow1 = 1, pow2 = 1;
    int best = 0;                                      // longest palindromic prefix found so far
    for (int i = 0; i < s.length(); i++) {
        long c = s.charAt(i);
        fwd1 = (fwd1 * B + c) % M1;                    // s[0..i] read left to right: new character is the lowest power
        fwd2 = (fwd2 * B + c) % M2;
        rev1 = (rev1 + c * pow1) % M1;                 // s[0..i] read right to left: new character is the highest power
        rev2 = (rev2 + c * pow2) % M2;
        pow1 = pow1 * B % M1;
        pow2 = pow2 * B % M2;
        if (fwd1 == rev1 && fwd2 == rev2) best = i + 1;
    }
    return s.length() - best;
}

Complexity. Time O(n): constant work per character. Space O(1).

The catch is that the answer is only correct with overwhelming probability, not with certainty. The Java file cross-checks it against the brute force on a thousand seeded random strings, but an adversary who knows B and M could construct a collision. The next approach is exact.

Approach 3: Optimal, KMP on `s + '$' + reverse(s)`

Intuition. The KMP prefix function answers this question exactly: for a string t, lps[i] is the length of the longest proper prefix of t[0..i] that is also a suffix of it. Build

t = s + '$' + reverse(s)

and look at the last value, lps[|t| - 1]: the longest prefix of t that is also a suffix of t.

The '$' occurs once in t, so such a border cannot contain it, and therefore has length at most n. It is a prefix of s on the left and a suffix of reverse(s) on the right.
A suffix of reverse(s) of length L is exactly the reverse of the prefix of s of length L. So the border is a prefix p of s with p == reverse(p): a palindromic prefix.
The prefix function returns the longest border, so we get the longest palindromic prefix.

Without the separator, the border could run across the junction: for s = "aa", t = "aaaa" has a border of length 3, which is longer than s itself.

Algorithm.

Build t = s + '$' + reverse(s).
Compute the prefix function: len is the current border length; on a mismatch fall back with len = lps[len - 1]; on a match extend it.
Return n - lps[|t| - 1].

static int optimal(String s) {
    int n = s.length();
    if (n == 0) return 0;
    String t = s + '$' + new StringBuilder(s).reverse();   // '$' must not occur in s
    int[] lps = new int[t.length()];
    int len = 0;
    for (int i = 1; i < t.length(); i++) {
        while (len > 0 && t.charAt(i) != t.charAt(len)) len = lps[len - 1];
        if (t.charAt(i) == t.charAt(len)) len++;
        lps[i] = len;
    }
    return n - lps[t.length() - 1];
}

Dry run on s = "abab", so t = "abab$baba":

i	0	1	2	3	4	5	6	7	8
t[i]	a	b	a	b	$	b	a	b	a
lps[i]	0	0	1	2	0	0	1	2	3

lps[8] = 3: the longest palindromic prefix is "aba", and the answer is 4 - 3 = 1 (insert "b" to get "babab").

Complexity. Time O(n): the prefix function on a string of length 2n + 1 is linear, because len rises by at most one per step and every fallback lowers it. Space O(n) for t and lps.

If s may contain every possible character, drop the separator altogether: compute the LPS array of s, then run the KMP matcher with pattern s over the text reverse(s). The number of matched characters after the last text character is the same longest palindromic prefix.

Edge cases and pitfalls

Front-only vs anywhere. "abb" needs 2 insertions at the front but only 1 anywhere ("abba"). Make sure you know which version you are asked.
Already a palindrome. "aba" returns 0; every approach finds the full-length prefix.
Empty string. Returns 0 from all three methods. The KMP method returns early only for clarity; without the guard, t would be "$" and the formula would still give 0.
Separator collisions. If '$' can appear in s, the border can cross the junction and the answer can be wrong. Choose a character outside the alphabet or use the separator-free matcher described above.
Hash collisions. The rolling-hash method is probabilistic. Use two moduli, or confirm the final candidate with a direct palindrome check.
Returning the string instead. If the palindrome itself is wanted, it is reverse(s.substring(L)) + s, where L is the prefix length found above.

Shortest Palindrome is the same reduction, returning the palindrome instead of the count.
Minimum insertions to make string palindrome - DP-29 allows insertions anywhere and is solved with DP.
KMP Algorithm or LPS array explains the prefix function used in Approach 3.
Longest happy prefix asks directly for the longest border of a string.
Rabin Karp Algorithm is built on the same rolling hashes as Approach 2.

Minimum insertions to make string palindrome

Problem

The reduction: keep the longest palindromic prefix

Approach 1: Brute force

Approach 2: Better, rolling hashes

Approach 3: Optimal, KMP on s + '$' + reverse(s)

Edge cases and pitfalls

Related problems

Approach 3: Optimal, KMP on `s + '$' + reverse(s)`