133 — Longest Palindromic Substring

133 — Longest Palindromic Substring

LeetCode 5 · Medium. Given a string s, return the longest substring of s that reads the same forwards and backwards.

---

🍽️ Intuition

Every palindrome has a center — either a single character (for odd-length palindromes like "aba") or a gap between two characters (for even-length palindromes like "abba"). Instead of asking "is this substring a palindrome?" for every one of the O(n^2) possible substrings, flip the question around: for every one of the 2n - 1 possible centers, how far can you expand outward before the two sides stop matching? That reframing turns "check a candidate" into "grow a candidate," and growing stops the instant it fails — no wasted comparisons on substrings that were never going to work.

---

🚩 Pattern-Recognition Cue

"Longest substring that reads the same forwards and backwards" is the palindrome-substring tell. Whenever the question is about the longest (not just counting) palindromic substring, expand-around-center is almost always the efficient path: pick every possible center, grow outward symmetrically, and track the widest successful expansion.

---

🐢 Brute Force

Check every possible substring for the palindrome property directly, using a straightforward O(n) two-pointer check per candidate.

func longestPalindromeBruteForce(_ s: String) -> String {
    let chars = Array(s)
    let n = chars.count
    guard n > 0 else { return "" }

    func isPalindrome(_ left: Int, _ right: Int) -> Bool {
        var l = left, r = right
        while l < r {
            if chars[l] != chars[r] { return false }
            l += 1
            r -= 1
        }
        return true
    }

    var bestStart = 0
    var bestLength = 1

    for start in 0..<n {
        for end in start..<n {
            let length = end - start + 1
            if length > bestLength && isPalindrome(start, end) {
                bestStart = start
                bestLength = length
            }
        }
    }

    return String(chars[bestStart..<(bestStart + bestLength)])
}

// smoke test
print(longestPalindromeBruteForce("babad"))   // "bab" (or "aba")
print(longestPalindromeBruteForce("cbbd"))    // "bb"
print(longestPalindromeBruteForce("a"))       // "a"

Big-O: O(n^3) time — O(n^2) substrings, each checked with an O(n) palindrome scan in the worst case. O(n) space for the chars array.

---

🚀 Optimal

For every possible center (both single-character and between-character centers), expand outward one step at a time while the two sides still match, and remember the widest successful expansion.

func longestPalindrome(_ s: String) -> String {
    let chars = Array(s)
    let n = chars.count
    guard n > 0 else { return "" }

    var bestStart = 0
    var bestLength = 1

    func expand(_ left: Int, _ right: Int) {
        var l = left, r = right
        while l >= 0 && r < n && chars[l] == chars[r] {
            l -= 1
            r += 1
        }
        // l, r overshot by one on both sides once the match broke (or a bound was hit)
        let length = r - l - 1
        if length > bestLength {
            bestLength = length
            bestStart = l + 1
        }
    }

    for center in 0..<n {
        expand(center, center)         // odd-length palindromes, centered on one character
        expand(center, center + 1)     // even-length palindromes, centered on a gap
    }

    return String(chars[bestStart..<(bestStart + bestLength)])
}

// smoke test — same cases as the brute force
print(longestPalindrome("babad"))   // "bab" (or "aba")
print(longestPalindrome("cbbd"))    // "bb"
print(longestPalindrome("a"))       // "a"

Big-O: O(n^2) time — 2n - 1 centers, each expansion taking up to O(n) steps in the worst case (e.g. all identical characters). O(n) space for the chars array, O(1) extra beyond that.

---

🔑 The Key Insight

The brute force treats "is this a palindrome?" as an independent question for every one of the O(n^2) substrings, paying a fresh O(n) scan each time even though most candidates fail almost immediately at their very outer edges. Expand-around-center flips the direction of the check: instead of validating a substring end-to-end, it grows a substring from the inside out and stops the instant a mismatch is found, so short-lived candidates cost almost nothing. Both approaches are ultimately bounded by O(n^2) total character comparisons in the worst case, but expand-around-center gets there by trying every center once (2n - 1 of them) rather than every substring once (O(n^2) of them, each independently re-scanned) — a smaller, non-redundant set of starting points doing the same job.

---

🔗 Related Chapters

• 1D Dynamic Programming — "is s[l...r] a palindrome?" has the classic 1-D-collapsed recurrence isPal(l, r) = (s[l] == s[r]) && isPal(l+1, r-1); expand-around-center walks that recurrence outward from the base case instead of filling a 2-D table.
• Two Pointers — expand is a textbook two-pointer walk, moving l and r outward in lockstep from a shared center until the matching condition breaks.
• Arrays and Strings — converting s to Array(s) up front gives O(1) indexed character access, which both versions rely on throughout.

---

🧸 Memory Sentence

Longest Palindromic Substring is grown, not checked — plant a center (on a character or between two), expand outward while the edges keep matching, and remember the widest expansion that ever succeeded.

---

✅ Check Your Understanding

1. Why does the loop call expand(center, center) and expand(center, center + 1) for every center, instead of just one of the two?
2. In expand, after the while loop exits, why is the palindrome's length r - l - 1 rather than r - l + 1?
3. For s = "cbbd", trace expand at center = 1 for both the odd and even calls. Which one produces the winning "bb", and why does the odd-centered call at center = 1 fail to beat length 1?

---

⬅️ Previous: House Robber II · Next: Palindromic Substrings ➡️