Longest Palindromic Substring (LC 5)

Pattern: Expand Around Center
Difficulty: Medium
Key Concept: Every palindrome has a center (one character for odd length, between two chars for even)—try all centers and expand while ends match.

Problem Statement

Given a string s, return the longest palindromic substring in s.

Input

• s: String — length up to ~1000 typical

Output

• String — any valid longest palindrome substring if several tie

Example

• s = "babad" → "bab" or "aba"
• s = "cbbd" → "bb"

---

1. Algorithm & Pseudocode

Brute force

Enumerate every substring, test palindrome by comparing symmetric pairs.

best = ""
for left from 0 to n-1:
    for right from left to n-1:
        if isPalindrome(s, left, right) and len > best.length():
            best = s[left..right]
return best

Optimal

For each center, expand:

best = ""
for center from 0 to n-1:
    expand odd center at center
    expand even center between center and center+1
return best

expand(l, r):
    while l>=0 and r<n and s[l]==s[r]:
        update best with s[l..r]
        l--; r++

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why centers A palindrome mirrors around its middle; enumerating centers covers all palindromes exactly once each (from their maximal expansion).

2. Odd vs even "aba" has a single middle b. "abba" has an empty middle between the two bs—handled by starting l=i, r=i vs l=i, r=i+1.

3. Why not only odd You would miss all even-length palindromes.

4. Time intuition There are O(n) centers; each expansion scans at most O(n) → O(n²) total—acceptable for n ≈ 1000.

---

3. The Dry Run

Sample: s = "babad". Centers (show one expansion).

Center index 2 (a), odd expansion

step	l	r	substring	match?
start	2	2	a	—
expand	1	3	bab	s[1]==s[3] (b/b)
expand	0	4	babad	s[0]!=s[4] stop

Longest at this center: bab (length 3).

ASCII

indices: 0 1 2 3 4
chars:   b a b a d
             ^ odd center at 2
           l     r  "bab" palindrome

---

4. Java Solution

Brute Force

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String best = "";
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j) && (j - i + 1) > best.length()) {
                    best = s.substring(i, j + 1);
                }
            }
        }
        return best;
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) {
                return false;
            }
        }
        return true;
    }
}

Time: O(n³) — O(n²) substrings × O(n) check.
Space: O(1) besides output substring.

Optimal

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int start = 0;
        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }
        return s.substring(start, start + maxLen);
    }

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

Time: O(n²).
Space: O(1).

---

5. The “Java vs. Others” Edge

• substring(start, endExclusive) After expansion, r - l - 1 is the palindrome length; converting to (start, maxLen) uses integer math i - (len - 1) / 2 to recover the left boundary for both odd/even centers.
• Manacher’s algorithm O(n) exists but is rarely required in interviews; expand-around-center is the bread-and-butter answer.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n³)	O(1)	Check every substring.
Expand around center	O(n²)	O(1)	Odd + even centers.
Manacher	O(n)	O(n)	Advanced; optional deep dive.