Algorithm

Longest Palindromic Substring

Arrays & Strings Pattern

Longest Palindromic Substring

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

CONSTRAINTS
  • 1 <= s.length <= 1000
  • s consists of digits and English letters
EXAMPLE 1
Input: s = "babad"
Output: "bab"
"bab" is a palindrome of length 3. "aba" is also length 3 and equally valid — either may be returned.
EXAMPLE 2
Input: s = "cbbd"
Output: "bb"
The only palindromes longer than one character sit around the middle "bb"; "cbbd" reversed is "dbbc", so the full string is not a palindrome.
EXAMPLE 3
Input: s = "a"
Output: "a"
A single character reads the same both ways, so it is a palindrome and the whole answer.
Is the answer a contiguous substring, or can it skip characters?
Contiguous — the characters must be adjacent. A skipping version would be the longest palindromic subsequence, a different (dynamic-programming) problem.
If several palindromes share the longest length, which do I return?
Any of them. For 'babad', both 'bab' and 'aba' have length 3, and either is accepted.
Is a single character a palindrome, and can the answer ever be empty?
A single character is a palindrome, and since s has length at least 1 the answer is always at least one character — never empty.
Is matching case-sensitive?
Yes. 'A' and 'a' are different characters, so 'Aa' is not a palindrome.

Finding the longest palindromic substring is a search for the widest mirrored symmetry within a string. The complexity of our solution depends on how much "memory" we use to avoid redundant checks.

The Brute Force (O(N³))

The most naive way is to check every possible substring. With N² substrings and an O(N) check for each, this is too slow for large inputs.

python
# Check every i, j pair (N^2), then check if palindrome (O(N))
for i in range(len(s)):
    for j in range(i, len(s)):
        sub = s[i : j+1]
        if sub == sub[::-1]:
            # update max...
Dynamic Programming (O(N²) Time, O(N²) Space)

We can avoid the O(N) check by noticing that "aba" is a palindrome ONLY IF its outer characters match ('a' == 'a') AND its inner substring ("b") is also a palindrome. We can store these boolean results in a 2D table to build longer palindromes from earlier, smaller results.

Expanding from Centers (O(N²) Time, O(1) Space)

This is the "gold standard" for interviews. Instead of building a table, we recognize that every palindrome radiates outward from a central point.

Odd vs. Even Symmetry:
- A palindrome can have an Odd Soul (centered on a single character like "aba").
- A palindrome can have an Even Soul (centered between two characters like "abba").

Because of this, we must test 2N - 1 potential centers: every character in the string, and every gap between characters. For each center, we use two pointers (L and R) and expand outward as long as the characters match.

python
def longestPalindrome(s):
    res = ""
    for i in range(len(s)):
        # 1. Expand from character (Odd: "aBa")
        p1 = expand(s, i, i)
        
        # 2. Expand from gap (Even: "aBBa")
        p2 = expand(s, i, i + 1)
        
        # Keep track of the longest one we've found
        res = max(res, p1, p2, key=len)
    return res

def expand(s, l, r):
    # Move pointers outward while characters match
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    # Return the valid palindrome found (slices are non-inclusive at the end)
    return s[l + 1 : r]
Manacher's Algorithm (O(N) Time)

The ultimate optimization. It uses the symmetry of previously found palindromes to "guess" the length of future ones, skipping almost all redundant expansions. While powerful, its complexity makes it a specialized tool rather than a standard interview requirement.

Worked Example:s = "babad"
0
b
1
a
L/R
2
b
3
a
4
d
We start expanding from the odd center character 'a' at index 1. The character itself forms a base palindrome of length 1.
0
b
L
1
a
2
b
R
3
a
4
d
We expand outward. Both L at index 0 ('b') and R at index 2 ('b') match, growing our palindrome to 'bab' of length 3.
0
b
1
a
2
b
3
a
4
d
Attempting to expand further makes L go out of bounds (index -1), so expansion for center 1 terminates. Our current max palindrome is 'bab'.
0
b
1
a
L
2
b
R
3
a
4
d
Next, we check the even-length center between index 1 ('a') and index 2 ('b'). Since they do not match, we cannot expand.
0
b
1
a
2
b
L/R
3
a
4
d
We move to the next odd center, character 'b' at index 2, and initialize our expansion.
0
b
1
a
L
2
b
3
a
R
4
d
We expand outward. L at index 1 ('a') and R at index 3 ('a') match, growing this palindrome to 'aba' of length 3.
0
b
L
1
a
2
b
3
a
4
d
R
We try to expand again. L at index 0 ('b') and R at index 4 ('d') do not match. The expansion terminates, leaving 'aba' as the result for center 2.
Interactive Strategy Visualization

Bilateral Spectrum

Expanding from symmetry kernels
b
a
b
a
d
📡

Ready to find the longest palindrome by expanding from centers.

O(N³) Brute Force
→
O(N²) Time · O(1) Space Center Expansion
→
O(N) Manacher