Longest Palindromic Substring

Difficulty: Medium Source: NeetCode

Problem

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

Example 1: Input: s = "babad" Output: "bab" (or "aba", both are valid)

Example 2: Input: s = "cbbd" Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consists of only digits and English letters

Prerequisites

Before attempting this problem, you should be comfortable with:

• Palindrome Checking — recognizing when a string reads the same forwards and backwards
• Two Pointers — expanding outward from a center
• String Indexing — working with substrings and indices

1. Brute Force

Intuition

Check every possible substring by trying all pairs of start and end indices. For each substring, verify if it’s a palindrome. Track the longest valid one found. Three nested operations: O(n²) pairs × O(n) palindrome check = O(n³) total.

Algorithm

1. For every pair (i, j) where i <= j, extract s[i:j+1].
2. Check if it’s a palindrome.
3. Track the longest palindrome found.
4. Return it.

Solution

def longestPalindrome_brute(s):
    n = len(s)
    best = s[0]

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

    return best


print(longestPalindrome_brute("babad"))   # "bab" or "aba"
print(longestPalindrome_brute("cbbd"))    # "bb"
print(longestPalindrome_brute("a"))       # "a"
print(longestPalindrome_brute("racecar")) # "racecar"

Complexity

• Time: O(n³) — n² substrings × O(n) palindrome check
• Space: O(n) — substring creation

2. Expand Around Center

Intuition

Every palindrome has a center. For a string of length n, there are 2n - 1 possible centers: each character (for odd-length palindromes) and each gap between characters (for even-length palindromes). Expand outward from each center as long as characters match. This finds all palindromes in O(n²) total — much better than brute force.

This is the “sweet spot” solution: simple to implement, fast in practice, and doesn’t require any complex data structures.

Algorithm

1. For each center position (single char and between chars):
   • Expand outward while s[left] == s[right].
   • Track the longest palindrome found.
2. Return the longest substring.

Solution

def longestPalindrome(s):
    n = len(s)
    start, max_len = 0, 1

    def expand(left, right):
        nonlocal start, max_len
        while left >= 0 and right < n and s[left] == s[right]:
            if right - left + 1 > max_len:
                start = left
                max_len = right - left + 1
            left -= 1
            right += 1

    for i in range(n):
        expand(i, i)      # odd-length palindromes centered at i
        expand(i, i + 1)  # even-length palindromes centered between i and i+1

    return s[start:start + max_len]


print(longestPalindrome("babad"))   # "bab"
print(longestPalindrome("cbbd"))    # "bb"
print(longestPalindrome("a"))       # "a"
print(longestPalindrome("racecar")) # "racecar"
print(longestPalindrome("abcba"))   # "abcba"
print(longestPalindrome("aacabdkacaa"))  # "aca" (first or last)

Complexity

• Time: O(n²) — n centers, each expanding up to O(n)
• Space: O(1) — only indices tracked

Common Pitfalls

Only checking odd-length palindromes. Expanding from a single character only finds odd-length palindromes like “aba”. You must also expand from gaps between characters to find even-length ones like “abba”.

Returning the substring directly vs tracking indices. Tracking (start, max_len) is cleaner and avoids creating many string objects. Return s[start:start+max_len] at the end.

Using sub == sub[::-1] in the brute force on large inputs. This creates an extra reversed copy of the string for every substring — it works but is slow. The expand approach avoids this entirely.