A complete visual walkthrough of the expand-around-center approach ā from brute force to elegant O(nĀ²) solution.
The naive approach: enumerate every possible substring, check if it is a palindrome, and track the longest one found.
For a string of length n, there are n(n+1)/2 substrings. Each palindrome check takes O(n) time, giving O(nĀ³) total.
We must check every substring at every starting position ā even after finding "bab", we continue checking the rest. This is wasteful.
O(nĀ³) is too slow. For n = 1000, that is up to 1 billion operations. We need an approach that avoids redundant checking. What if we could grow palindromes outward from their centers instead?
Every palindrome has a center. For odd-length palindromes, the center is a single character. For even-length palindromes, the center is the gap between two characters.
For a string of length n, there are 2n - 1 possible centers (n single-character centers + n-1 between-character centers). From each center, we expand outward while characters match.
The key advantage: expansion stops the moment characters do not match. We never check substrings that cannot possibly be palindromes. Each expansion takes at most O(n), and there are O(n) centers, giving us O(nĀ²) total ā a huge improvement over brute force.
Let's trace through "babad" step by step, expanding from each center.
Cannot expand left (at boundary). Palindrome: "b" (length 1)
s[0]='b' == s[2]='b'? Yes! Expand further: s[-1] is out of bounds. Stop.
Palindrome: "bab" (length 3) ā new best!
s[1]='a' == s[3]='a'? Yes! Expand: s[0]='b' == s[4]='d'? No! Stop.
Palindrome: "aba" (length 3) ā ties the best.
No adjacent duplicates in "babad", so no even-length palindromes longer than 0.
Result: "bab" (or "aba") ā both are length 3 palindromes found by expanding from centers at index 1 and 2 respectively. The algorithm returns whichever it finds first.
s[1]='b' == s[2]='b'? Yes! Expand: s[0]='c' == s[3]='d'? No! Stop. Palindrome: "bb" (length 2)
The expand-around-center approach handles all edge cases naturally, without special-case code.
No special-case code needed. The loop naturally handles single characters (expansion returns 1), all-same characters (expansion reaches boundaries), and no-palindrome cases (each center yields length 1). The only guard is for null/empty input.
class Solution { public String longestPalindrome(String s) { // Guard: handle null or empty input if (s == null || s.length() < 1) return ""; int start = 0, maxLen = 0; // Try every possible center for (int i = 0; i < s.length(); i++) { // Odd-length palindrome: single char center int len1 = expand(s, i, i); // Even-length palindrome: two char center int len2 = expand(s, i, i + 1); // Take the longer of the two expansions int len = Math.max(len1, len2); // Update best if this palindrome is longer if (len > maxLen) { maxLen = len; // Calculate the starting index of this palindrome start = i - (len - 1) / 2; } } return s.substring(start, start + maxLen); } // Expand outward from center while chars match private int expand(String s, int left, int right) { // Keep expanding while in bounds and chars match while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; // move left pointer outward right++; // move right pointer outward } // Length of palindrome found // (left and right have moved one step past the palindrome) return right - left - 1; } }
Why right - left - 1? When the while loop exits, left and right have each moved one step beyond the palindrome boundaries. So the actual palindrome spans from left+1 to right-1, giving length (right-1) - (left+1) + 1 = right - left - 1.
Why start = i - (len - 1) / 2? The center is at index i. For a palindrome of length len, the left edge is (len-1)/2 positions before the center. Integer division handles both odd and even lengths correctly.
Enter a string and step through the expand-around-center algorithm. Watch both odd and even expansions at each center.
We iterate through 2n - 1 centers, and each expansion can take up to O(n) in the worst case (e.g., "aaaa...a"). No extra arrays or matrices are needed ā just a few integer variables to track the best palindrome.
Why not Manacher's? Manacher's algorithm achieves O(n) by reusing previously computed palindrome information. However, the expand-around-center approach is far simpler, uses O(1) space, and is the expected solution for interviews. O(nĀ²) comfortably handles the constraint of n ā¤ 1000.