Longest Palindromic Substring (LeetCode 5)

The problem

Given a string s, return its longest contiguous substring that reads the same forwards and backwards. If there are ties, any one of them is accepted.

Input:  s = "babad"
Output: "bab"

"bab" and "aba" are both length-3 palindromes; nothing of length 4 or 5 is.

How to think about it

Start with brute force. Check every substring (O(n²) of them) and test each for being a palindrome in O(n). That is O(n³).

The DP view. s[i..j] is a palindrome if s[i] == s[j] and s[i+1..j-1] is a palindrome. A 2-D boolean table built on that rule gives O(n²) time and O(n²) space. It works, but the table is fiddly to fill in the right order.

The key insight: grow palindromes from their middle. Every palindrome has a centre: a single character (odd length, like "aba") or the gap between two equal characters (even length, like "abba"). There are only 2n - 1 centres. From each one, expand outwards while the characters on both sides match. That uses the same “inner part must be a palindrome” rule as the DP, but checks it on the fly with O(1) extra space.

Which pattern is this? The palindrome DP, done as centre expansion. The tell is “longest palindromic substring” (contiguous). For a subsequence, you need the real 2-D table.

Approach

1. If s is empty, return "". Track the best palindrome as start, end.
2. expand(l, r) moves l left and r right while both are in range and s[l] == s[r], then returns the last valid bounds (l + 1, r - 1).
3. For each index i, expand from (i, i) (odd centre) and (i, i + 1) (even centre). If either gives a longer span, update start, end.
4. Return s[start:end + 1].

Solution

def longest_palindrome(s):
    if not s: return ""
    start, end = 0, 0                             # best palindrome so far is s[start..end]
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1; r += 1   # grow while ends match
        return l+1, r-1                           # last bounds that matched
    for i in range(len(s)):
        for l, r in (expand(i, i), expand(i, i+1)):   # odd centre, even centre
            if r - l > end - start: start, end = l, r
    return s[start:end+1]
# longest_palindrome("babad") -> "bab" (or "aba")

Dry run

On s = "babad":

At i = 2, "aba" has the same length as "bab", so it doesn’t replace it (the comparison is strict). The result is “bab”.

Complexity

• Time: O(n²). There are 2n - 1 centres, and each expansion can run up to O(n) steps.
• Space: O(1) beyond the output string.

Edge cases and pitfalls

• Empty string returns ""; one character returns itself.
• Forgetting even centres misses answers like "abba" in "cabbad".
• All the same character ("aaaa") is the worst case for time but still returns the whole string.
• Manacher’s algorithm solves it in O(n), but it’s rarely expected; mention it as a follow-up.

Related problems

• Palindromic Substrings (LeetCode 647): the same centre expansion, counting palindromes instead of keeping the longest.
• Longest Palindromic Subsequence (LeetCode 516): the non-contiguous version, which needs a 2-D table.
• Valid Palindrome (LeetCode 125): the two-pointer palindrome check, moving inwards instead of outwards.