LeetCode 5: Longest Palindromic Substring

Problem Restatement

We are given a string s.

We need to return the longest substring that is a palindrome.

A palindrome reads the same forward and backward.

Examples:

"aba"
"racecar"
"bb"

All of these are palindromes.

A substring must be contiguous.

For example:

"aceca"

is a substring of "racecar".

But:

"rcar"

is not contiguous, so it is not a substring.

The problem asks for the substring itself, not its length.

The LeetCode statement allows multiple valid answers if several longest palindromes have the same length. (leetcode.com)

Input and Output

Example function shape:

def longestPalindrome(s: str) -> str:
    ...

Examples

Example 1:

s = "babad"

Possible answers:

"bab"
"aba"

Both are correct because both have length 3.

Example 2:

s = "cbbd"

The answer is:

"bb"

Example 3:

s = "a"

A single character is always a palindrome.

So the answer is:

"a"

Example 4:

s = "ac"

The longest palindrome has length 1.

So either:

"a"

or:

"c"

is valid.

First Thought: Check Every Substring

One possible approach:

1. Generate every substring.
2. Check whether it is a palindrome.
3. Keep the longest one.

To check whether a string is a palindrome:

sub == sub[::-1]

Code:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        best = ""

        for i in range(len(s)):
            for j in range(i, len(s)):
                sub = s[i:j + 1]

                if sub == sub[::-1]:
                    if len(sub) > len(best):
                        best = sub

        return best

Problem With Brute Force

There are many substrings.

For a string of length n:

• Number of substrings: O(n^2)
• Palindrome check per substring: O(n)

Total complexity:

This becomes too slow for longer strings.

Key Insight

A palindrome mirrors around its center.

Example:

racecar
   ^

The center is:

e

Characters expand symmetrically:

c == c
a == a
r == r

Another example:

abba
  ^^

Even-length palindromes have two center characters.

So every palindrome comes from one of two center types:

Instead of checking every substring, we expand outward from every possible center.

Expand Around Center

Suppose:

s = "babad"

Choose center:

"a"

Expand left and right:

b a b

Still valid.

Expand again:

outside bounds

Stop.

We found:

"bab"

Now consider even length:

s = "cbbd"

Center between the two b characters:

b | b

Expand outward:

bb

Next expansion:

c != d

Stop.

We found:

"bb"

Algorithm

For every index i:

1. Expand around center (i, i) for odd-length palindromes.
2. Expand around center (i, i + 1) for even-length palindromes.
3. Keep the longer result.

The expansion process:

• While:
  • indices stay inside bounds
  • and characters match
• Move:
  • left pointer left
  • right pointer right

When expansion stops, the palindrome is the region between them.

Correctness

Every palindrome has a center.

For odd-length palindromes, the center is one character.

For even-length palindromes, the center is the gap between two characters.

The algorithm explicitly tries both possibilities at every position.

During expansion, the algorithm only continues while:

s[left] == s[right]

So the current substring always remains a palindrome.

When expansion stops, one of two things happened:

1. The pointers left the string bounds.
2. The characters no longer matched.

Therefore the largest valid palindrome around that center has already been found.

Since the algorithm checks every possible center, it eventually checks the center of the global longest palindrome.

So the algorithm returns the longest palindromic substring.

Complexity

This is much faster than the brute-force O(n^3) approach.

Implementation

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

            return s[left + 1:right]

        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

Code Explanation

The helper function:

expand(left, right)

tries to grow a palindrome outward.

The loop condition:

s[left] == s[right]

ensures the substring stays symmetric.

When the loop ends, the pointers have moved one step too far.

So the correct palindrome is:

s[left + 1:right]

We then try every possible center:

for i in range(len(s)):

Odd-length center:

expand(i, i)

Even-length center:

expand(i, i + 1)

Whenever a longer palindrome appears, we update:

best

Finally:

return best

Testing

def run_tests():
    s = Solution()

    assert s.longestPalindrome("babad") in ["bab", "aba"]
    assert s.longestPalindrome("cbbd") == "bb"
    assert s.longestPalindrome("a") == "a"
    assert s.longestPalindrome("ac") in ["a", "c"]
    assert s.longestPalindrome("racecar") == "racecar"
    assert s.longestPalindrome("aaaa") == "aaaa"
    assert s.longestPalindrome("abcda") in ["a", "b", "c", "d"]

    print("all tests passed")

run_tests()