Loading…

hardStringsSometimes asked

Longest Palindromic Substring — Manacher's Algorithm

Q: How do you solve Longest Palindromic Substring — Manacher's Algorithm using the Expand Around Center approach?

When to use it: This is the realistic interview answer — give it confidently before mentioning Manacher. It's simple, correct, and usually fast enough. Expand-around-center grows palindromes outward from every possible middle. **Centers, not substrings.** Every palindrome has a center: a single character for odd lengths, or the gap between two characters for even lengths. There are `n` odd centers and `n−1` even centers, `2n−1` in total — far fewer than the `n²` substrings the brute force checks. **The expansion.** From a center, set a left pointer and a right pointer and move them outward while `s[left] == s[right]` and both stay in bounds. When they stop, `s[left+1..right−1]` is the maximal palindrome at that center. Compare its length to the best so far. **Handling both parities.** Run the expansion twice per index `i`: once with `left = right = i` (odd-length palindrome centered on a character), once with `left = i, right = i+1` (even-length palindrome centered in the gap). Take the longer. **Why it's the right default.** It's short, hard to get wrong, and `O(n²)` clears typical constraints (`n ≤ a few thousand`) comfortably. State it first; only escalate to Manacher when the interviewer pins the input size at something that needs linear time. Time complexity: O(n²). Space complexity: O(1).

Arrays & Hashing · 38 of 83 · 14 min

Given a string s, return the longest substring of s that is a palindrome (reads identically forwards and backwards).

If several palindromes share the maximum length, returning any one of them is acceptable. A single character is a palindrome of length 1.

In plain English

You're locating the widest mirror-symmetric contiguous block. The naive idea checks every substring; expand-around-center grows outward from each possible center; Manacher removes the remaining redundancy by reusing palindrome radii already discovered, via the symmetry inside the rightmost known palindrome. The `#`-transform is the trick that collapses the even/odd center cases into one.

Examples

Example 1

Input: s = "babad"
Output: "bab" (or "aba")
Note: Both "bab" and "aba" have length 3; either is a valid longest palindrome.

Example 2

Input: s = "cbbd"
Output: "bb"
Note: Even-length palindrome; the #-transform makes its center a separator so the same odd-length machinery finds it.

Example 3

Input: s = "a"
Output: "a"
Note: Single character — palindrome of length 1.

Constraints

1 ≤ n ≤ 10⁶ (Manacher); expand-around-center handles up to ~10⁴
ASCII characters; the separator `#` must not appear in s (or use a sentinel not in the alphabet)
Substrings are contiguous
Return any one longest palindrome if there are ties

Clarifying questions4First question: Substring or subsequence?Explore questions

Q1.Substring or subsequence?
Substring — contiguous. Longest palindromic subsequence is a separate DP problem.
Q2.Do I need O(n), or is O(n²) acceptable?
Decides the approach. Expand-around-center (O(n²)) is the expected default; reach for Manacher only when the input forces O(n).
Q3.Are ties acceptable?
Yes — return any longest palindrome. Track the first or last maximum, your choice.
Q4.Can I assume a separator character is available?
For Manacher, yes — `#` works if it isn't in the alphabet; otherwise pick a byte outside the input's character set.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find the longest substring that reads the same forwards and backwards. Expand-around-center is O(n²) and is the answer most candidates should reach. Manacher's algorithm gets it to O(n): transform the string by inserting separators so every palindrome is odd-length, then sweep left to right maintaining the rightmost palindrome [center, right]. Inside that boundary you seed each radius from its mirror before expanding, so each character is examined O(1) amortized times.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can first give the clean O(n²) expand-around-center, then explain why naive checking is wasteful and how mirror symmetry inside a known palindrome removes the redundancy.

Where candidates slip

Botching the index mapping between the transformed and original strings, or forgetting the min(right − i, mirror) cap so symmetry is assumed past the verified boundary.

How to stand out

Lead with expand-around-center (the realistic interview answer), then derive Manacher's mirror trick and the right-never-moves-back invariant, and convert p[i] back to original coordinates correctly.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Expand Around Center	`O(n²)`	`O(1)`	This is the realistic interview answer — give it confidently before mentioning Manacher. It's simple, correct, and usually fast enough.	Read
2	Manacher's Algorithm (Optimal)Optimal	`O(n)`	`O(n)`	Bring it out when O(n) is required. Frame it as 'the Z-algorithm trick for palindromes': transform to kill the even/odd split, then reuse mirror radii inside the rightmost palindrome.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Three rungs from brute force to Manacher

How to read it:Most interviews want the middle rung; Manacher is the O(n) summit for hard constraints.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Expand Around Center

TimeO(n²)SpaceO(1)

This is the realistic interview answer — give it confidently before mentioning Manacher. It's simple, correct, and usually fast enough.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A palindrome is defined by its center. How many centers are there? n single-character centers (odd length) plus n−1 gaps between characters (even length) → 2n−1 centers.

2Hint 2Explore hint

From each center, expand two pointers outward while the characters match and stay in bounds. The widest expansion over all centers is the answer.

3Hint 3Explore hint

Track the best (start, length) seen. Each expansion is O(n) and there are O(n) centers → O(n²).

A · Core idea

Expand-around-center grows palindromes outward from every possible middle.

Centers, not substrings. Every palindrome has a center: a single character for odd lengths, or the gap between two characters for even lengths. There are n odd centers and n−1 even centers, 2n−1 in total — far fewer than the n² substrings the brute force checks.

The expansion. From a center, set a left pointer and a right pointer and move them outward while s[left] == s[right] and both stay in bounds. When they stop, s[left+1..right−1] is the maximal palindrome at that center. Compare its length to the best so far.

Handling both parities. Run the expansion twice per index i: once with left = right = i (odd-length palindrome centered on a character), once with left = i, right = i+1 (even-length palindrome centered in the gap). Take the longer.

Why it's the right default. It's short, hard to get wrong, and O(n²) clears typical constraints (n ≤ a few thousand) comfortably. State it first; only escalate to Manacher when the interviewer pins the input size at something that needs linear time.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "babad"

Array state

center 1

l=r=1 ('a')

[0]

l ↓r ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result"bab"

C · Code with teaching comments

Reference implementation previewpublic class ExpandCenter { public String longestPalindrome(String s) { if (s.isEmpty()) return ""; int start = 0, end = 0; for (int i = 0; i < s.length(); i++) {Explore the full code

solution.javaJava

Expand Around Center — reference

3 teaching notes

1
public class ExpandCenter {
2
    public String longestPalindrome(String s) {
3
        if (s.isEmpty()) return "";
4
        int start = 0, end = 0;
5
        for (int i = 0; i < s.length(); i++) {
6
            // Odd-length palindrome centered on character i.
7
            int odd = expand(s, i, i);
8
            // Even-length palindrome centered in the gap after i.
9
            int even = expand(s, i, i + 1);
10
            int len = Math.max(odd, even);
11
            if (len > end - start + 1) {
12
                start = i - (len - 1) / 2;
13
                end = i + len / 2;
14
            }
15
        }
16
        return s.substring(start, end + 1);
17
    }
18
 
19
    private int expand(String s, int l, int r) {
20
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
21
            l--; r++;
22
        }
23
        // After the loop overshoots by one on each side, r−l−1 is the matched length.
24
        return r - l - 1;
25
    }
26
 
27
    public static void main(String[] args) {
28
        System.out.println(new ExpandCenter().longestPalindrome("babad"));
29
    }
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

The leap from O(n³) to O(n²) is realizing you don't enumerate substrings — you enumerate the 2n−1 centers and let each palindrome reveal its own length by expanding. Manacher's further leap is noticing that neighboring centers' expansions overlap, so many comparisons are redundant.

ComplexityO(n²) time, O(1) space — There are 2n−1 centers; each expansion can grow up to n/2 steps → O(n²) total. Only a few indices of bookkeeping → O(1) extra space.

E · Edge cases and pitfalls3Handling only odd centers and missing even-length palindromes like "bb".Explore edge cases

Pitfalls

Handling only odd centers and missing even-length palindromes like "bb".
Wrong start/end recovery from the returned length — off-by-one on (len−1)/2.
Re-deriving substrings instead of expanding from centers (back to O(n³)).

03.2

Approach 2 of 2 · Optimal

Manacher's Algorithm (Optimal)

TimeO(n)SpaceO(n)

Bring it out when O(n) is required. Frame it as 'the Z-algorithm trick for palindromes': transform to kill the even/odd split, then reuse mirror radii inside the rightmost palindrome.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Even and odd palindromes are annoying because they have different center types. Insert a separator like '#' between every character and at both ends: "abba" → "#a#b#b#a#". Now every palindrome is odd-length and centered on a real position.

2Hint 2Explore hint

Define p[i] as the radius of the palindrome centered at transformed index i. Maintain the rightmost palindrome you've seen as [center, right].

3Hint 3Explore hint

If i is inside [center, right], its mirror j = 2*center − i already has a known radius. Seed p[i] = min(right − i, p[j]) — capped because beyond 'right' you haven't checked symmetry — then expand explicitly. If you pass 'right', move the window.

A · Core idea

Manacher's algorithm computes, in linear time, the palindrome radius at every center by reusing symmetry the way the Z-algorithm reuses prefix matches.

Step 1 — the transform removes the parity split. Build t by inserting a separator # between every pair of characters and at both ends: "abba" becomes "#a#b#b#a#". This has two effects. First, t always has odd length 2n+1, so every palindrome in t is odd-length and centered on a single index — the even/odd case distinction disappears. Second, because of the padding, the radius p[i] of the palindrome centered at t[i] equals the length of the corresponding palindrome in the original string. That coincidence is what makes the bookkeeping clean.

Step 2 — the rightmost-palindrome window. Sweep i left to right over t, maintaining center and right, the center and right edge of the palindrome discovered so far that reaches farthest right (right = center + p[center]).

Step 3 — borrow from the mirror. When processing i, if i < right, then i lies inside the current palindrome, which is symmetric about center. Its mirror index is j = 2*center − i. By symmetry, the palindrome at i is at least as wide as the one at j — up to the boundary. So seed p[i] = min(right − i, p[j]). The min is essential: beyond right the characters were never compared, so you can't assume the mirror's full radius carries over. If i >= right, start with p[i] = 0.

Step 4 — expand and slide. After seeding, try to extend: while t[i + p[i] + 1] == t[i − p[i] − 1], increment p[i]. These comparisons happen only past the current right. If the new palindrome reaches beyond right, update center = i, right = i + p[i].

Why it's linear. Every successful character comparison advances right, and right moves only forward across 2n+1 positions. So across the entire sweep there are at most O(n) successful comparisons, plus one failing comparison per index. The mirror seeding is constant time. That's the whole O(n) argument — identical in spirit to the Z-algorithm's monotone r.

Step 5 — map back. The answer length is max(p[i]). The starting index in the original string for that center is (i − p[i]) / 2, because each original character sits at an odd transformed index and the # padding doubles positions. Slice the original string from there for p[i] characters.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abba" → t = "#a#b#b#a#"

Array state

i=5

inside window; mirror = 2·4−5 = 3

[0]

[1]

[2]

[3]

c ↓

[4]

i ↓

[5]

[6]

[7]

[8]

Current pointerResolved stateNot processed

Final result"abba"

C · Code with teaching comments

solution.javaJava

Manacher's Algorithm (Optimal) — optimal

6 teaching notes

1
public class Manacher {
2
    public String longestPalindrome(String s) {
3
        if (s.isEmpty()) return "";
4
        StringBuilder sb = new StringBuilder("#");
5
        // Build "#a#b#...#" so every palindrome is odd-length and centered on a real
6
        // index.
7
        for (char c : s.toCharArray()) { sb.append(c).append('#'); }
8
        String t = sb.toString();
9
        int m = t.length();
10
        int[] p = new int[m];
11
        int center = 0, right = 0;
12
        int bestLen = 0, bestCenter = 0;
13
        for (int i = 0; i < m; i++) {
14
            if (i < right) {
15
                // Reflect i across the current center to find the already-computed
16
                // radius to borrow.
17
                int mirror = 2 * center - i;
18
                // Cap the borrowed radius at the boundary — symmetry past 'right' is
19
                // unverified.
20
                p[i] = Math.min(right - i, p[mirror]);
21
            }
22
            while (i - p[i] - 1 >= 0 && i + p[i] + 1 < m
23
                    && t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) {
24
                p[i]++;
25
            }
26
            // Found a palindrome reaching farther right → slide the window; right never
27
            // retreats.
28
            if (i + p[i] > right) { center = i; right = i + p[i]; }
29
            if (p[i] > bestLen) { bestLen = p[i]; bestCenter = i; }
30
        }
31
        // Convert the transformed center/radius back to the original start index.
32
        int start = (bestCenter - bestLen) / 2;
33
        return s.substring(start, start + bestLen);
34
    }
35
 
36
    public static void main(String[] args) {
37
        System.out.println(new Manacher().longestPalindrome("abba"));
38
        System.out.println(new Manacher().longestPalindrome("babad"));
39
    }
40
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.40 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Manacher is Z-thinking for palindromes. The #-transform turns 'two kinds of palindrome' into 'one kind', and the rightmost-palindrome window lets each new center inherit its mirror's radius for free, paying real comparisons only when it extends past everything seen — which, because the boundary only moves forward, totals linear work. Use it only when O(n) is mandatory; otherwise expand-around-center is the saner choice.

ComplexityO(n) time, O(n) space — Each explicit expansion step increases 'right', and 'right' only ever moves forward across the 2n+1 transformed positions. So the total expansion work is O(n). The mirror seeding is O(1) per index. Building the transformed string and mapping back are O(n). Total O(n) time, O(n) space for the transform and the p array.

E · Edge cases and pitfalls7s = "cbbd" — Transform puts a '#' center between the b's; the algorithm finds even-length "bb".Explore edge cases

Edge cases handled

s = "cbbd"Transform puts a '#' center between the b's; the algorithm finds even-length "bb".
s = "aaaa"Nested palindromes; mirror reuse seeds most radii, expansion stays O(n) overall.
s = "a"t = "#a#"; p = [0,1,0]; best length 1 → "a".

Pitfalls

Omitting the min(right − i, p[mirror]) cap — assumes symmetry past the verified boundary.
Wrong mapping back: original start is (center − radius) / 2; off-by-one corrupts the answer.
Letting 'right' move backward — breaks the linear-time guarantee.
Reaching for Manacher when O(n²) was fine — extra complexity, more chances to introduce bugs.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic class Manacher { public String longestPalindrome(String s) { if (s.isEmpty()) return ""; StringBuilder sb = new StringBuilder("#"); for (char c : s.toCharArray()) { sb.append(c).append('#'); }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public class Manacher {
    public String longestPalindrome(String s) {
        if (s.isEmpty()) return "";
        StringBuilder sb = new StringBuilder("#");
        for (char c : s.toCharArray()) { sb.append(c).append('#'); }
        String t = sb.toString();
        int m = t.length();
        int[] p = new int[m];
        int center = 0, right = 0;
        int bestLen = 0, bestCenter = 0;
        for (int i = 0; i < m; i++) {
            if (i < right) {
                int mirror = 2 * center - i;
                p[i] = Math.min(right - i, p[mirror]);
            }
            while (i - p[i] - 1 >= 0 && i + p[i] + 1 < m
                    && t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) {
                p[i]++;
            }
            if (i + p[i] > right) { center = i; right = i + p[i]; }
            if (p[i] > bestLen) { bestLen = p[i]; bestCenter = i; }
        }
        int start = (bestCenter - bestLen) / 2;
        return s.substring(start, start + bestLen);
    }

public static void main(String[] args) {
        System.out.println(new Manacher().longestPalindrome("abba"));
        System.out.println(new Manacher().longestPalindrome("babad"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the boundary cap on the mirror

Beyond 'right' the characters were never compared. Copying the full mirror radius assumes symmetry you haven't verified and over-reports the palindrome length.

Explore the code comparison

Don't write this

if i < right:
    p[i] = p[2 * center - i]   # ignores the boundary

Write this instead

if i < right:
    p[i] = min(right - i, p[2 * center - i])

Wrong index mapping back to the original

Each original character sits at an odd transformed index. The start in the original string is (center − radius) // 2; using center − radius (without /2) slices the wrong substring.

Explore the code comparison

Don't write this

start = best_center - best_len      # transformed coordinates, wrong

Write this instead

start = (best_center - best_len) // 2

Using Manacher where expand-around-center suffices

Manacher is intricate and easy to get subtly wrong under interview pressure. If O(n²) clears the constraints, the simpler center expansion is the safer, more communicable answer.

Explore the code comparison

Don't write this

# n <= 1000 but candidate writes full Manacher with index bugs

Write this instead

# n <= 1000: expand-around-center, O(n^2), simple and correct

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Mirror reuse inside the rightmost palindrome boundary (like Z, for palindromes)

Code pattern to memorize

transform: "#a#b#a#"  (n -> 2n+1, all palindromes odd)
p[i] = radius of palindrome centered at transformed index i
if i < right: p[i] = min(right - i, p[mirror])   mirror = 2*center - i
expand while chars match; if i + p[i] > right: center = i, right = i + p[i]
answer length = max(p[i]); original start = (i - p[i]) / 2

Rules to remember

1Insert separators (#) between and around every character so even- and odd-length palindromes both become odd in the transformed string — one case to handle, not two.
2p[i] in the transformed string equals the palindrome length in the original string (a neat consequence of the # padding).
3Inside the current [center, right], seed p[i] from its mirror 2*center − i, capped at `right − i` — past right you haven't verified symmetry.
4Only the explicit expansion can push right rightward, and right never retreats — that monotonicity is the O(n) proof, exactly as in the Z-algorithm.
5Map back carefully: original start index is (i − p[i]) / 2. Off-by-one here is the most common Manacher bug.

Use this pattern when

Longest palindromic substring with a strict O(n) requirement
Counting all palindromic substrings in linear time
Queries about palindrome radii at every center
When expand-around-center's O(n²) is too slow for the input size

Choose another pattern when

n is small or O(n²) is acceptable → expand-around-center is far simpler and less bug-prone
You need longest palindromic *subsequence* (non-contiguous) → that's DP, not Manacher
Only checking if the whole string is a palindrome → two pointers, O(n), no transform
Counting distinct palindromes → palindromic tree (Eertree), a different structure

Interview takeaway

Manacher is the Z-algorithm idea applied to palindromes: the `#`-transform removes the odd/even split, and a rightmost-palindrome window lets each new center borrow its mirror's radius before expanding. Reach for it only when O(n) is genuinely required.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternMirror-reuse within a rightmost boundary — the same engine as the Z-algorithm, specialized to palindromes via the #-transform. Recognise it for linear-time palindrome radius/length queries; otherwise expand-around-center is the pragmatic default.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count All Palindromic Substrings
Coming soon
Sum (p[i] + 1) // 2 over Manacher's radii, or count expansions in the center method.
Longest Palindromic Subsequence
Coming soon
Different problem — non-contiguous — solved with interval DP, not Manacher.
Shortest Palindrome (prepend characters)
Coming soon
Use KMP on s + '#' + reverse(s) to find the longest palindromic prefix.
Palindrome Partitioning (min cuts)
Coming soon
Precompute palindrome boundaries (Manacher or DP) then DP over cut positions.

Same pattern

Palindrome Index

←

Lexicographic Rank of a String

Continue · Next problem

Pattern Search — KMP (Knuth–Morris–Pratt)

hardStringsSometimes asked

Longest Palindromic Substring — Manacher's Algorithm

Arrays & Hashing · 38 of 83 · 14 min

Given a string s, return the longest substring of s that is a palindrome (reads identically forwards and backwards).

If several palindromes share the maximum length, returning any one of them is acceptable. A single character is a palindrome of length 1.

In plain English

Examples

Example 1

Input: s = "babad"
Output: "bab" (or "aba")
Note: Both "bab" and "aba" have length 3; either is a valid longest palindrome.

Example 2

Input: s = "cbbd"
Output: "bb"
Note: Even-length palindrome; the #-transform makes its center a separator so the same odd-length machinery finds it.

Example 3

Input: s = "a"
Output: "a"
Note: Single character — palindrome of length 1.

Constraints

1 ≤ n ≤ 10⁶ (Manacher); expand-around-center handles up to ~10⁴
ASCII characters; the separator `#` must not appear in s (or use a sentinel not in the alphabet)
Substrings are contiguous
Return any one longest palindrome if there are ties

Clarifying questions4First question: Substring or subsequence?Explore questions

Q1.Substring or subsequence?
Substring — contiguous. Longest palindromic subsequence is a separate DP problem.
Q2.Do I need O(n), or is O(n²) acceptable?
Decides the approach. Expand-around-center (O(n²)) is the expected default; reach for Manacher only when the input forces O(n).
Q3.Are ties acceptable?
Yes — return any longest palindrome. Track the first or last maximum, your choice.
Q4.Can I assume a separator character is available?
For Manacher, yes — `#` works if it isn't in the alphabet; otherwise pick a byte outside the input's character set.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can first give the clean O(n²) expand-around-center, then explain why naive checking is wasteful and how mirror symmetry inside a known palindrome removes the redundancy.

Where candidates slip

Botching the index mapping between the transformed and original strings, or forgetting the min(right − i, mirror) cap so symmetry is assumed past the verified boundary.

How to stand out

Lead with expand-around-center (the realistic interview answer), then derive Manacher's mirror trick and the right-never-moves-back invariant, and convert p[i] back to original coordinates correctly.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Expand Around Center	`O(n²)`	`O(1)`	This is the realistic interview answer — give it confidently before mentioning Manacher. It's simple, correct, and usually fast enough.	Read
2	Manacher's Algorithm (Optimal)Optimal	`O(n)`	`O(n)`	Bring it out when O(n) is required. Frame it as 'the Z-algorithm trick for palindromes': transform to kill the even/odd split, then reuse mirror radii inside the rightmost palindrome.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Three rungs from brute force to Manacher

How to read it:Most interviews want the middle rung; Manacher is the O(n) summit for hard constraints.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Expand Around Center

TimeO(n²)SpaceO(1)

This is the realistic interview answer — give it confidently before mentioning Manacher. It's simple, correct, and usually fast enough.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A palindrome is defined by its center. How many centers are there? n single-character centers (odd length) plus n−1 gaps between characters (even length) → 2n−1 centers.

2Hint 2Explore hint

From each center, expand two pointers outward while the characters match and stay in bounds. The widest expansion over all centers is the answer.

3Hint 3Explore hint

Track the best (start, length) seen. Each expansion is O(n) and there are O(n) centers → O(n²).

A · Core idea

Expand-around-center grows palindromes outward from every possible middle.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "babad"

Array state

center 1

l=r=1 ('a')

[0]

l ↓r ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result"bab"

C · Code with teaching comments

solution.javaJava

Expand Around Center — reference

3 teaching notes

1
public class ExpandCenter {
2
    public String longestPalindrome(String s) {
3
        if (s.isEmpty()) return "";
4
        int start = 0, end = 0;
5
        for (int i = 0; i < s.length(); i++) {
6
            // Odd-length palindrome centered on character i.
7
            int odd = expand(s, i, i);
8
            // Even-length palindrome centered in the gap after i.
9
            int even = expand(s, i, i + 1);
10
            int len = Math.max(odd, even);
11
            if (len > end - start + 1) {
12
                start = i - (len - 1) / 2;
13
                end = i + len / 2;
14
            }
15
        }
16
        return s.substring(start, end + 1);
17
    }
18
 
19
    private int expand(String s, int l, int r) {
20
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
21
            l--; r++;
22
        }
23
        // After the loop overshoots by one on each side, r−l−1 is the matched length.
24
        return r - l - 1;
25
    }
26
 
27
    public static void main(String[] args) {
28
        System.out.println(new ExpandCenter().longestPalindrome("babad"));
29
    }
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — There are 2n−1 centers; each expansion can grow up to n/2 steps → O(n²) total. Only a few indices of bookkeeping → O(1) extra space.

E · Edge cases and pitfalls3Handling only odd centers and missing even-length palindromes like "bb".Explore edge cases

Pitfalls

Handling only odd centers and missing even-length palindromes like "bb".
Wrong start/end recovery from the returned length — off-by-one on (len−1)/2.
Re-deriving substrings instead of expanding from centers (back to O(n³)).

03.2

Approach 2 of 2 · Optimal

Manacher's Algorithm (Optimal)

TimeO(n)SpaceO(n)

Bring it out when O(n) is required. Frame it as 'the Z-algorithm trick for palindromes': transform to kill the even/odd split, then reuse mirror radii inside the rightmost palindrome.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

2Hint 2Explore hint

Define p[i] as the radius of the palindrome centered at transformed index i. Maintain the rightmost palindrome you've seen as [center, right].

3Hint 3Explore hint

A · Core idea

Manacher's algorithm computes, in linear time, the palindrome radius at every center by reusing symmetry the way the Z-algorithm reuses prefix matches.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abba" → t = "#a#b#b#a#"

Array state

i=5

inside window; mirror = 2·4−5 = 3

[0]

[1]

[2]

[3]

c ↓

[4]

i ↓

[5]

[6]

[7]

[8]

Current pointerResolved stateNot processed

Final result"abba"

C · Code with teaching comments

solution.javaJava

Manacher's Algorithm (Optimal) — optimal

6 teaching notes

1
public class Manacher {
2
    public String longestPalindrome(String s) {
3
        if (s.isEmpty()) return "";
4
        StringBuilder sb = new StringBuilder("#");
5
        // Build "#a#b#...#" so every palindrome is odd-length and centered on a real
6
        // index.
7
        for (char c : s.toCharArray()) { sb.append(c).append('#'); }
8
        String t = sb.toString();
9
        int m = t.length();
10
        int[] p = new int[m];
11
        int center = 0, right = 0;
12
        int bestLen = 0, bestCenter = 0;
13
        for (int i = 0; i < m; i++) {
14
            if (i < right) {
15
                // Reflect i across the current center to find the already-computed
16
                // radius to borrow.
17
                int mirror = 2 * center - i;
18
                // Cap the borrowed radius at the boundary — symmetry past 'right' is
19
                // unverified.
20
                p[i] = Math.min(right - i, p[mirror]);
21
            }
22
            while (i - p[i] - 1 >= 0 && i + p[i] + 1 < m
23
                    && t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) {
24
                p[i]++;
25
            }
26
            // Found a palindrome reaching farther right → slide the window; right never
27
            // retreats.
28
            if (i + p[i] > right) { center = i; right = i + p[i]; }
29
            if (p[i] > bestLen) { bestLen = p[i]; bestCenter = i; }
30
        }
31
        // Convert the transformed center/radius back to the original start index.
32
        int start = (bestCenter - bestLen) / 2;
33
        return s.substring(start, start + bestLen);
34
    }
35
 
36
    public static void main(String[] args) {
37
        System.out.println(new Manacher().longestPalindrome("abba"));
38
        System.out.println(new Manacher().longestPalindrome("babad"));
39
    }
40
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.40 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7s = "cbbd" — Transform puts a '#' center between the b's; the algorithm finds even-length "bb".Explore edge cases

Edge cases handled

s = "cbbd"Transform puts a '#' center between the b's; the algorithm finds even-length "bb".
s = "aaaa"Nested palindromes; mirror reuse seeds most radii, expansion stays O(n) overall.
s = "a"t = "#a#"; p = [0,1,0]; best length 1 → "a".

Pitfalls

Omitting the min(right − i, p[mirror]) cap — assumes symmetry past the verified boundary.
Wrong mapping back: original start is (center − radius) / 2; off-by-one corrupts the answer.
Letting 'right' move backward — breaks the linear-time guarantee.
Reaching for Manacher when O(n²) was fine — extra complexity, more chances to introduce bugs.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

public static void main(String[] args) {
        System.out.println(new Manacher().longestPalindrome("abba"));
        System.out.println(new Manacher().longestPalindrome("babad"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the boundary cap on the mirror

Beyond 'right' the characters were never compared. Copying the full mirror radius assumes symmetry you haven't verified and over-reports the palindrome length.

Explore the code comparison

Don't write this

if i < right:
    p[i] = p[2 * center - i]   # ignores the boundary

Write this instead

if i < right:
    p[i] = min(right - i, p[2 * center - i])

Wrong index mapping back to the original

Each original character sits at an odd transformed index. The start in the original string is (center − radius) // 2; using center − radius (without /2) slices the wrong substring.

Explore the code comparison

Don't write this

start = best_center - best_len      # transformed coordinates, wrong

Write this instead

start = (best_center - best_len) // 2

Using Manacher where expand-around-center suffices

Manacher is intricate and easy to get subtly wrong under interview pressure. If O(n²) clears the constraints, the simpler center expansion is the safer, more communicable answer.

Explore the code comparison

Don't write this

# n <= 1000 but candidate writes full Manacher with index bugs

Write this instead

# n <= 1000: expand-around-center, O(n^2), simple and correct

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Mirror reuse inside the rightmost palindrome boundary (like Z, for palindromes)

Code pattern to memorize

transform: "#a#b#a#"  (n -> 2n+1, all palindromes odd)
p[i] = radius of palindrome centered at transformed index i
if i < right: p[i] = min(right - i, p[mirror])   mirror = 2*center - i
expand while chars match; if i + p[i] > right: center = i, right = i + p[i]
answer length = max(p[i]); original start = (i - p[i]) / 2

Rules to remember

1Insert separators (#) between and around every character so even- and odd-length palindromes both become odd in the transformed string — one case to handle, not two.
2p[i] in the transformed string equals the palindrome length in the original string (a neat consequence of the # padding).
3Inside the current [center, right], seed p[i] from its mirror 2*center − i, capped at `right − i` — past right you haven't verified symmetry.
4Only the explicit expansion can push right rightward, and right never retreats — that monotonicity is the O(n) proof, exactly as in the Z-algorithm.
5Map back carefully: original start index is (i − p[i]) / 2. Off-by-one here is the most common Manacher bug.

Use this pattern when

Longest palindromic substring with a strict O(n) requirement
Counting all palindromic substrings in linear time
Queries about palindrome radii at every center
When expand-around-center's O(n²) is too slow for the input size

Choose another pattern when

n is small or O(n²) is acceptable → expand-around-center is far simpler and less bug-prone
You need longest palindromic *subsequence* (non-contiguous) → that's DP, not Manacher
Only checking if the whole string is a palindrome → two pointers, O(n), no transform
Counting distinct palindromes → palindromic tree (Eertree), a different structure

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count All Palindromic Substrings
Coming soon
Sum (p[i] + 1) // 2 over Manacher's radii, or count expansions in the center method.
Longest Palindromic Subsequence
Coming soon
Different problem — non-contiguous — solved with interval DP, not Manacher.
Shortest Palindrome (prepend characters)
Coming soon
Use KMP on s + '#' + reverse(s) to find the longest palindromic prefix.
Palindrome Partitioning (min cuts)
Coming soon
Precompute palindrome boundaries (Manacher or DP) then DP over cut positions.

Same pattern

Palindrome Index

←

Lexicographic Rank of a String

Continue · Next problem

Pattern Search — KMP (Knuth–Morris–Pratt)