Palindromes

A string equal to its own reverse. The recurring difficulty is the odd/even distinction, which every technique handles in its own way.

The toolkit

Task	Method	Cost
Is $s[l..r]$ a palindrome?	forward + reverse hashes	$O(1)$
Longest palindromic substring	Manacher	$O(n)$
Longest palindromic substring	hashing + binary search per centre	$O(n\log n)$
Count distinct palindromic substrings	Eertree	$O(n)$
Count all palindromic substrings (with multiplicity)	Manacher: $\sum \lceil d_i/2\rceil$	$O(n)$
Longest palindromic subsequence	LCS of $s$ and $\mathrm{reverse}(s)$	$O(n^2)$
Minimum insertions to make a palindrome	$n-\mathrm{LPS}$	$O(n^2)$
Minimum cuts into palindromes	DP + a palindrome table	$O(n^2)$
Palindromic factorisation into $k$ parts	DP over Eertree series links	$O(n\log n)$
Shortest palindrome by prepending	prefix function of $s+\#+\mathrm{reverse}(s)$	$O(n)$

Manacher’s algorithm

Computes, for every centre, the radius of the longest palindrome around it, in $O(n)$. Handle odd and even centres either with two arrays or by inserting separators:

string t = "^";
for (char c : s) { t += '#'; t += c; }
t += "#$";                                        // sentinels prevent bounds checks
vector<int> p(t.size(), 0);
int c = 0, r = 0;
for (int i = 1; i + 1 < (int)t.size(); i++) {
    if (i < r) p[i] = min(r - i, p[2*c - i]);     // mirror
    while (t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++;
    if (i + p[i] > r) { c = i; r = i + p[i]; }
}

p[i] is then the length of the palindrome centred at $i$ in the original string. The separator trick makes every palindrome odd-length, removing the case split entirely — worth the doubled array.

The mirror-and-extend structure is identical to the Z-function’s Z-box; learning one teaches the other.

The hashing alternative

Two hashes (forward and reverse) plus a binary search on the radius gives $O(n\log n)$ and about ten lines. For most problems that is enough, and it generalises to variants Manacher cannot express (palindromes with one mismatch allowed, weighted palindromes).

bool isPal(int l, int r) { return fwd.get(l, r) == rev.get(n-1-r, n-1-l); }

Palindromic tree (Eertree)

The specialist structure: $O(n)$ nodes, one per distinct palindromic substring — and a string of length $n$ has at most $n$ distinct palindromic substrings, a non-obvious fact that makes the structure linear. See Palindromic Tree.

It is the right tool when the problem is about distinct palindromes or about palindromic factorisations.

Facts worth knowing

• A string of length $n$ has at most $n$ distinct palindromic substrings.
• Every string can be factored into palindromes (single characters are palindromes); the minimum number is computable in $O(n\log n)$ with Eertree series links.
• A string is a palindrome iff its longest border of length $\ge n/2$ pattern holds — more usefully, palindromes of a string form $O(\log n)$ arithmetic progressions by length, which is what makes the $O(n\log n)$ factorisation possible.
• Rearrangement into a palindrome is possible iff at most one character has an odd count — a counting check, not a string algorithm.
• The number of palindromic substrings of aaa...a is $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$ with multiplicity but only $n$ distinct.

Common problem shapes

1. “Longest palindromic substring” → Manacher, or hashing + binary search.
2. “Count palindromic substrings” → Manacher (with multiplicity) or Eertree (distinct).
3. “Minimum cuts into palindromes” → precompute isPal[i][j] in $O(n^2)$, then a linear DP.
4. “Make it a palindrome with minimum insertions” → $n$ − longest palindromic subsequence.
5. “Is every prefix a palindrome” / “shortest palindrome by prepending” → prefix function on $s+\#+\mathrm{reverse}(s)$.
6. “Palindromic pairs among $n$ words” → hash each word and its reverse, then match.

See also: Manacher · Palindromic Tree · String Hashing