Longest Palindrome in a String

Time: O(n^2)

Space: O(1)

Problem Overview

Expand around each center.

Intuition

Expand around each center. For each character (and each gap between characters), expand outward as long as characters match. Track the maximum expansion. O(n²) time, O(1) space.

Algorithm

1For each center (2n-1 centers for odd + even): expand while valid.
2ExpandAroundCenter(left, right): while left>=0 and right<n and s[left]==s[right]: left--, right++.
3Track max length and start index.

Example Walkthrough

Input: s = "babad"

1. Center at i=1("a"): expand → "bab"(len=3). Center at i=2("b"): expand → "aba"(len=3).
2. Return "bab" (first found).

Output: "bab"

Common Pitfalls

• Check both odd (single-char center) and even (between-char center) palindromes.

Longest Palindrome in a String.java

Java

// Approach: Expand-around-center for each character and each pair. Track max palindrome found.
// Time: O(n^2) Space: O(1)
class Solution {
    static String longestPalindrome(String s) {
        int maxLength = 0;
        String longest = "";

        for (int i = 0; i < s.length(); i++) {

            String odd = check(s, i, i);
            if (odd.length() > maxLength) {
                maxLength = odd.length();
                longest = odd;
            }

            String even = check(s, i, i + 1);
            if (even.length() > maxLength) {
                maxLength = even.length();
                longest = even;
            }
        }

        return longest;
    }

    static String check(String s, int left, int right) {
        
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }

        return s.substring(left + 1, right);
    }
}

Was this solution helpful?