5. Longest Palindromic Substring

Problem¶

Given a string s, return any longest contiguous substring that is a palindrome.

Example:

s = "babad" -> "bab"   # "aba" is also valid

Key trick¶

Expand around every possible center.

Every palindrome is centered either on:
- one character, like "aba"
- the gap between two characters, like "abba"
For each center, grow left and right while characters match.
Keep the longest range found.

Trap¶

Common mistakes:

Forgetting even-length palindromes like "bb".
Returning a subsequence instead of a substring.
Re-slicing strings inside the inner loop too much.
Off-by-one errors on bounds.
Assuming the answer is unique for cases like "babad".

Why is it interesting?¶

It looks like DP or brute force, but the clean interview solution is center expansion.

Brute force is \(O(n^3)\).
Center expansion is simple and \(O(n^2)\) with \(O(1)\) extra space.
It tests string indexing, edge cases, and clear reasoning.

Python solution¶

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Best palindrome boundaries: s[best_l:best_r + 1]
        best_l = 0
        best_r = 0

        def expand(l, r):
            # Grow while s[l:r+1] stays palindrome.
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1

            # Loop exits one step after valid palindrome.
            return l + 1, r - 1

        for i in range(len(s)):
            # Odd-length palindrome centered at i.
            l1, r1 = expand(i, i)

            # Even-length palindrome centered between i and i + 1.
            l2, r2 = expand(i, i + 1)

            if r1 - l1 > best_r - best_l:
                best_l, best_r = l1, r1

            if r2 - l2 > best_r - best_l:
                best_l, best_r = l2, r2

        return s[best_l:best_r + 1]

Comment on my solution¶

Your solution is correct and interview-valid.

Good parts:

Uses the right idea: expand around center.
Handles both odd and even palindromes.
Time/space complexity is right: \(O(n^2)\) and \(O(1)\) extra space.

What I would improve:

Track indices instead of storing sliced substrings during expansion.
len(ch) is always 1, so that line is unnecessary.
Repeating the same expansion logic twice is a bit noisy; a helper makes it cleaner.
Slicing inside the loop creates extra strings repeatedly.

A small fix in your style would be to update only boundaries during expansion, then slice once at the end.

## Solution
class Solution:
    def longestPalindrome(self, s: str) -> str:
        best_palin = ""
        # we grow sliding window around mid until the string in the
        # sliding window no longer is a palindrome
        for mid, ch in enumerate(s):
            best_palin = best_palin if len(ch) < len(best_palin) else ch

            # even palindrome centered in mid
            left, right = mid - 1, mid
            while -1 < left and right < len(s):
                if s[left] != s[right]:
                    break
                best_palin = best_palin if right - left + 1 < len(best_palin) else s[left:right + 1]
                left -= 1
                right += 1

            # odd palindrome centered in mid
            left, right = mid - 1, mid + 1
            while -1 < left and right < len(s):
                if s[left] != s[right]:
                    break
                best_palin = best_palin if right - left + 1 < len(best_palin) else s[left:right + 1]
                left -= 1
                right += 1
        return best_palin

Solution().longestPalindrome("babad") # 'aba'