5. Longest Palindromic Substring

For each character (and each pair of characters), expand outward as long as the palindrome holds. Track the longest.

Approach

1. For each index, try expanding from center (odd-length and even-length).
2. Expand while characters match.
3. Track start and length of the longest palindrome found.

Complexity

• Time: O(n^2)
• Space: O(1)

class Solution {
    private int start = 0;
    private int maxLen = 1;

    public String longestPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
            expand(s, i, i);
            expand(s, i, i + 1);
        }
        return s.substring(start, start + maxLen);
    }

    private void expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            if (r - l + 1 > maxLen) {
                start = l;
                maxLen = r - l + 1;
            }
            l--;
            r++;
        }
    }
}