Palindrome search gets expensive fast when every center has to expand outward from the beginning with no memory of what was already found. Manacher’s Algorithm cuts out that repeated checking by carrying forward palindrome length data from earlier positions, so a center inside a larger confirmed match can start with information that is already available before any fresh character comparisons begin. That reuse gives the algorithm a linear-time scan while still finding the longest palindromic substring and the palindrome radius at every center. In Java, arrays and index-based access fit this logic naturally, so the full process is easier to follow than it first appears.
Why Repeated Expansion Becomes Expensive
Most palindrome checks begin with a center and grow outward one step at a time while the characters on both sides still match. That starting idea is easy to follow because every palindrome has some middle point. Odd-length palindromes place that middle on a character, as with racecar, while even-length palindromes place it between two characters, as with abba.
The slowdown starts because neighboring centers overlap so heavily. A long match found at one center does not automatically help the next center beside it, so the scan ends up rechecking part of the same region again. Small strings can hide that cost, but wider palindromic spans make the repeated comparisons add up quickly.
Center Expansion From Scratch
Basic center expansion treats every center as if nothing has already been learned. Pick an index, grow outward, stop at the first mismatch, then move to the next index and do nearly the same scan again. That behavior can hide inside compact code because each expansion loop is short. The total cost only becomes obvious when the full pass across the string is viewed as a whole.
Take abacaba for example, starting from the middle finds a long palindrome. Move one center to the left and the scan still covers a shorter palindrome that overlaps heavily with the earlier result. Move one more center and part of that same region gets checked again. Strings such as aaaaaaa make the repetition easier to notice, because nearly every center expands across a wide span. Each center is valid on its own, but the full search keeps paying for the same character comparisons again and again.
This Java helper shows the basic expansion rule:
public static int expandAroundCenter(String text, int left, int right) {
while (left >= 0 && right < text.length()
&& text.charAt(left) == text.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}Left and right move outward while the characters match, and the returned value gives the palindrome length for that single center.
Finding the longest substring with that helper means calling it across the full string:
public static String longestPalindromeByExpansion(String text) {
if (text == null || text.isEmpty()) {
return "";
}
int bestStart = 0;
int bestLength = 1;
for (int i = 0; i < text.length(); i++) {
int oddLength = expandAroundCenter(text, i, i);
int evenLength = expandAroundCenter(text, i, i + 1);
int currentLength = Math.max(oddLength, evenLength);
if (currentLength > bestLength) {
bestLength = currentLength;
bestStart = i - (currentLength - 1) / 2;
}
}
return text.substring(bestStart, bestStart + bestLength);
}Odd centers call expandAroundCenter(text, i, i). Even centers call expandAroundCenter(text, i, i + 1). That covers both palindrome forms, but it also means each position or gap starts a fresh expansion with no stored radius data from nearby centers.
Counting comparisons makes the repeated cost easier to track:
public static int countComparisons(String text, int left, int right) {
int comparisons = 0;
while (left >= 0 && right < text.length()) {
comparisons++;
if (text.charAt(left) != text.charAt(right)) {
break;
}
left--;
right++;
}
return comparisons;
}Call this method at every center on a string filled with repeated characters and the total comparison count climbs much faster than the input length. That is why the worst-case time cost for center expansion is usually treated as O(n²). The outer scan visits each center, and the inner loop can travel far for a large share of those centers.
The expensive part is not the long expansion at a single center. Cost grows because nearby centers keep revisiting overlapping territory from the beginning. That wording gets closer to the real source of the slowdown than a bare statement that the method is quadratic.
Odd and even centers add more repetition because strings like abbaabba need character-based centers and gap-based centers to cover every case. That full coverage is correct and useful for learning palindromes, but it still doubles the set of starting points. Nothing is carried forward from an earlier expansion, so overlapping checks keep returning.
Why Mirrored Radii Help
Mirrored radius data changes the question from what this center can prove from zero to what has already been proved near its mirrored partner. That single change removes a large share of the repeated comparison cost.
Let’s say a long palindrome has already been found around some midpoint. Any center inside that span has a matching center on the other side of the midpoint. If the left-side center already has a stored radius, the mirrored center on the right begins with part of its own answer already available before any new comparison starts.
We can see that borrowing step in this Java helper:
public static int borrowedRadius(int[] radii, int currentCenter, int currentRight, int index) {
int mirror = 2 * currentCenter - index;
if (index >= currentRight) {
return 0;
}
return Math.min(currentRight - index, radii[mirror]);
}If the current index falls outside the known right edge, borrowing is not possible and the start radius stays at 0. If the index is inside that known span, the mirrored center supplies a starting radius. Math.min caps that borrowed value so it never claims more than the current right edge can support.
That cap is important. Mirrored centers can store a large radius, yet not all of it is safe to copy. Part of that palindrome may extend into territory the current center has not proved on its side. Borrowed radius data gives a trusted starting length, not always the final length.
Take a region where a known palindrome runs from index 4 to index 14, with center 9. Look at index 11. Its mirror across center 9 is index 7. If the stored radius at index 7 is 2, then index 11 can begin with radius 2 as long as that borrowed length stays inside the known right boundary. Inner characters do not need to be compared again. Fresh comparison starts only after that borrowed distance ends.
This brief calculation makes the index relationship easier to trace:
int currentCenter = 9;
int currentRight = 14;
int index = 11;
int mirror = 2 * currentCenter - index;
int mirroredRadius = 2;
int startRadius = Math.min(currentRight - index, mirroredRadius);startRadius equals 2, so index 11 does not restart from radius 0. Expansion begins farther out, near the boundary of what still has to be checked.
That idea forms the bridge between basic center expansion and the later linear-time scan. Earlier center-by-center search repeats inner comparisons at nearby positions. Mirrored radii remove that repetition by carrying forward what earlier centers already proved. New checks still happen, but they begin closer to the unexplored edge, which is why the total comparison count drops so sharply across the full string.
How Manacher’s Algorithm Works in Java
After the repeated overlap problem is known, the next step is to see how Manacher’s Algorithm reorganizes the scan. Instead of treating every center as a separate outward expansion with no carried-forward length data, it restructures the string into a format where every palindrome behaves like the same kind of object. From there, the algorithm keeps track of the farthest confirmed right edge and borrows radius data from mirrored centers whenever that borrowed length is already supported by the palindrome currently in view. Java works great for this logic because arrays, integer indexing, and loops make the moving parts easy to trace from left to right.
Turning Every Palindrome Into One Center Style
Odd-length palindromes and even-length palindromes create an awkward split if both are handled as two unrelated cases. racecar has a middle character. abba has a middle gap. Without some kind of reformatting, a palindrome scan has to keep remembering which kind of center it is dealing with at each step.
Manacher’s Algorithm removes that split by placing separator positions between characters and at both ends. After that change, every palindrome has a center at a single index in the transformed layout. The original string abba can be viewed like this in a teaching-only layout:
public static String visualLayout(String text) {
StringBuilder layout = new StringBuilder("^");
for (int i = 0; i < text.length(); i++) {
layout.append('|').append(text.charAt(i));
}
layout.append("|$");
return layout.toString();
}Calling visualLayout("abba") produces ^|a|b|b|a|$. The even palindrome now has a center at the separator between the two b values, while odd palindromes also still have a center of their own. That means the scan no longer needs separate logic for odd and even cases.
This string-based view is helpful for learning, but the later full Java version is better off keeping the transformed layout in an int[] rather than a String. Fixed separator characters such as | or # can collide with data already present in the input. An integer layout avoids that issue by reserving sentinel values that do not overlap with real Unicode code points. That transformed layout does more than make the string look uniform. It also gives the radius array a uniform meaning. Each entry records how far a palindrome extends from its center in the transformed space. There is no branch for odd length and no second branch for even length. Every center expands by checking one step left and one step right inside the same layout.
Mapped back to the original string, that means an odd palindrome such as aba and an even palindrome such as abba both become radius problems with the same rules. When that reformatted view is in place, later parts of the algorithm can focus on boundary tracking and borrowed radius values without having to worry about two separate center types.
Tracking the Active Right Boundary
Two running values drive the scan after the transformed layout is ready. One holds the center of the palindrome that currently reaches farthest to the right. The other holds that palindrome’s right edge. Those two values are usually named center and right.
As the scan moves from left to right, each new index asks a very narrow question. Does this index fall inside the current right boundary, or has it gone past it. That small check determines how much prior radius data can be trusted before any new outward expansion begins.
If an index falls outside the current right edge, no borrowed radius is available yet. Expansion begins at radius 0, because nothing about that new center has been confirmed by the earlier rightmost palindrome.
If an index falls inside the right edge, then part of the answer is already known. The current rightmost palindrome gives a safe zone where symmetry can be trusted. The scan does not need to restart from zero at that index. Instead, it can begin from a radius value supported by the palindrome already in view. This is also where the linear-time behavior starts to become easier to see. Fresh outward comparison only happens when a center reaches beyond the old right boundary. Every successful push beyond that boundary moves right farther to the right, and that boundary never moves backward. Total outward boundary growth across the full scan therefore stays proportional to the input length, which is a big part of why the total time stays at O(n).
The algorithm is still checking centers from left to right, but the scan is no longer blind. It carries a live right boundary and a live center from the farthest-reaching palindrome found so far. That running state changes the full traversal from a sequence of isolated expansions into a connected pass where earlier radius data continues to inform later positions.
Reusing Mirrored Data Safely
Symmetry is where the saved comparisons come from. When an index falls inside the current right boundary, there is a mirrored index on the opposite side of the current center. Radius data already stored at that mirrored position can give the current index a starting radius before any new character check begins.
The mirror index comes from a short arithmetic rule:
int mirror = 2 * center - i;If i is inside the active right boundary, the algorithm can borrow radius data from radius[mirror]. Still, that borrowed value cannot blindly cross the current right edge. The right boundary marks the farthest territory already confirmed by the current enclosing palindrome, so borrowed length has to stop there if the mirrored radius extends farther.
We can see an example of this here:
if (i < right) {
radius[i] = Math.min(right - i, radius[mirror]);
}right - i is the maximum radius that stays fully inside the current boundary from index i. radius[mirror] is the amount already known at the mirrored position. Taking the smaller of those two values keeps the borrowed radius inside territory that is already verified by symmetry.
Fresh expansion starts after that borrowed radius has been assigned.
while (layout[i + radius[i] + 1] == layout[i - radius[i] - 1]) {
radius[i]++;
}That loop does not repeat the inner comparisons already supported by the current rightmost palindrome. It begins at the first position that still needs new confirmation. This is the reason mirrored data removes so much repeated checking. The algorithm is not copying the full answer from the mirror every time. It is copying the part that is already justified by the active boundary, then asking for new comparisons only beyond that.
Three situations can come up around that mirrored radius idea. Sometimes the mirrored radius stays fully inside the current right edge. In that case, the borrowed value can be accepted as-is. Sometimes the mirrored radius runs past the left side of the enclosing palindrome, which means only part of it is safe to reuse. In the third case, the current index is outside the right boundary, so no borrowed value is available and expansion begins from zero.
There is one other thing to keep in mind for the scan. Borrowed radius data is never treated as a blind shortcut. It is only trusted within the span already supported by the current enclosing palindrome. New expansion still happens, but it starts at the edge of known territory instead of at the center. That is what cuts away the repeated inner checks that slowed down basic center expansion.
Java Code for the Longest Palindromic Substring
The full Java code makes the moving parts easier to connect from start to finish. The version below returns the longest palindromic substring in O(n) time with O(n) extra space. It reads the string as Unicode code points rather than raw UTF-16 char values, so supplementary characters stay intact.
public final class ManacherLongestPalindrome {
private ManacherLongestPalindrome() {
}
public static String longestPalindrome(String text) {
if (text == null || text.isEmpty()) {
return "";
}
int[] original = text.codePoints().toArray();
int[] layout = toLayout(original);
int[] radius = new int[layout.length];
int center = 0;
int right = 0;
int bestCenter = 0;
int bestRadius = 0;
for (int i = 1; i < layout.length - 1; i++) {
int mirror = 2 * center - i;
if (i < right) {
radius[i] = Math.min(right - i, radius[mirror]);
}
while (layout[i + radius[i] + 1] == layout[i - radius[i] - 1]) {
radius[i]++;
}
if (i + radius[i] > right) {
center = i;
right = i + radius[i];
}
if (radius[i] > bestRadius) {
bestRadius = radius[i];
bestCenter = i;
}
}
int start = (bestCenter - bestRadius) / 2;
return new String(original, start, bestRadius);
}
private static int[] toLayout(int[] original) {
int[] layout = new int[original.length * 2 + 3];
layout[0] = -1;
int j = 1;
for (int codePoint : original) {
layout[j++] = -3;
layout[j++] = codePoint;
}
layout[j++] = -3;
layout[j] = -2;
return layout;
}
}text.codePoints().toArray() reads the input as Unicode code points. That avoids splitting supplementary characters into two UTF-16 units, which would throw off palindrome comparisons for some text.
toLayout() builds the transformed array. Negative integers act as sentinels and separators, while real code points remain non-negative. The left sentinel at index 0 and the right sentinel at the last slot let the expansion loop stop naturally at both ends without extra boundary checks inside the while condition.
radius[i] holds the palindrome radius for transformed index i. center and right track the active palindrome that currently reaches farthest to the right. mirror gives the reflected position across center, which is where borrowed radius data comes from when i falls inside the active boundary.
The line int start = (bestCenter - bestRadius) / 2; maps the transformed layout back to the original code point array. That division by 2 comes from the separator layout, where every original code point is separated by one inserted slot.
Look at the result for abba. In the transformed layout, the longest palindrome grows around a separator center rather than around a character center. Look at racecar, and the longest palindrome grows around a code point center. Both cases still end up with a single radius value in the transformed array, which is exactly why this reformatted layout is so useful for the rest of the scan.
The full scan still visits each transformed index, but fresh outward comparison only happens at the edge of borrowed radius information. That keeps the total time at O(n). Extra space stays at O(n) because the code holds the original code point array, the transformed layout, and the radius array.
Conclusion
Manacher’s Algorithm gets its speed from the way it reorganizes palindrome search into a single left-to-right pass with carried-forward radius data. After the string is transformed so every palindrome uses the same center format, the scan can track the current rightmost palindrome, borrow safe radius length from mirrored positions, and only compare new characters when the known boundary can be pushed farther. In Java, that logic fits naturally into arrays and index math, which makes the full process easier to trace from the transformed layout all the way back to the longest palindromic substring.