Longest Palindromic Substring

A palindrome is defined by its center: every palindrome, once you strip its outermost matching characters, is a smaller palindrome around the same center (or the same center itself). So instead of checking every substring, you can walk through every possible center – there are 2n - 1 of them, one per character (odd-length palindromes) and one per gap between characters (even-length palindromes) – and grow outward from each as far as the characters keep matching.

Brute Force

Time O(n³)Space O(1)

Check every substring directly: for each start and end position, verify whether that substring reads the same backwards, and keep the longest one that does.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def isPalindrome(sub: str) -> bool:
            return sub == sub[::-1]

        best = ""
        n = len(s)
        for i in range(n):
            for j in range(i, n):
                sub = s[i:j + 1]
                if len(sub) > len(best) and isPalindrome(sub):
                    best = sub
        return best

There are O(n²) substrings, and checking each one for being a palindrome costs O(n) → O(n³) time, O(1) extra space (ignoring the substrings themselves).

Expand Around Center

OptimalTime O(n²)Space O(1)

For each of the 2n - 1 centers, expand a left and right pointer outward while the characters they point at keep matching. Track the longest palindrome found. Odd-length palindromes start with l = r = i; even-length ones start with l = i, r = i + 1.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(l: int, r: int) -> str:
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return s[l + 1:r]

        best = ""
        for i in range(len(s)):
            odd = expand(i, i)
            if len(odd) > len(best):
                best = odd
            even = expand(i, i + 1)
            if len(even) > len(best):
                best = even
        return best

Trace for s = "babad" (indices 0..4 hold b a b a d):

best = "b"

1 / 5

comparingresultcurrentdiscarded

Odd center i=0: single char "b" is trivially a palindrome of length 1.

Each of the n centers can expand up to O(n) times → O(n²) time. Only a constant number of pointers are kept at once → O(1) space. This beats the O(n²) 2-D dp[i][j] table approach (which also solves the problem correctly, but needs O(n²) space to store which substrings are palindromes) while keeping the same time complexity.