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

Watch each index tried as an odd and an even center: the pointers l and r keep moving outward while the end characters match, and the final candidate s[l+1:r] only replaces best when it is strictly longer.

before the scanl = – · r = –

Checks inside the while loop

no comparisons this step

candidate s[l+1:r]

empty

best

empty

1 / 12

currentcomparingresultdiscardedseen

Every palindrome has a center. Each index i is tried twice: odd centers start at (i, i) and even centers at (i, i + 1). Pointers then grow outward while the end characters keep matching.

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.

Longest Palindromic Substring

Brute Force

Expand Around Center

More 1-D DP practice