LeetCode 5 · 1-D DP

Longest Palindromic Substring, explained with a picture

A mirror sliding along the letters.

Medium1-D DP
▶ Watch it step by step

The problem

Given a string, return its longest palindromic substring: the longest block of consecutive letters that reads the same backwards.

Input:  "cbabad"
Output: "bab"   ("aba" is equally long)

Picture it

Picture placing a small mirror at every possible centre: on a letter (for odd-length palindromes) or between two letters (for even ones). From each mirror we expand outward one letter on each side while both sides match. The widest stretch we ever reach is the answer.

How to recognise it

  • You want the longest block of consecutive letters that reads the same backwards (a substring, not a subsequence).
  • A palindrome is symmetric around its centre, so it can be grown outwards one letter on each side while the two ends match.
  • The string has at most 1,000 characters, which allows O(n²) work but not O(n³).
  • Any question of the form "best contiguous piece with a symmetry property" invites expanding around a centre or a table of "is s[i..j] a palindrome".

Start with brute force

Check every substring, longest first, and return the first one that equals its own reverse.

def longest_palindrome_brute(s):
    n = len(s)
    for size in range(n, 0, -1):             # longest first
        for start in range(n - size + 1):
            piece = s[start:start + size]
            if piece == piece[::-1]:
                return piece
    return ""

There are about n²/2 substrings and each check costs up to O(n), so time is O(n³): for n = 1,000 that is roughly 1.7 × 10^8 character steps even before the cost of building slices. Space is O(n) for the slices.

From brute force to the idea

  1. Find the waste. To test s[i:j+1] the brute force compares from scratch, although a palindrome is just a smaller palindrome with the same letter added on both sides.
  2. Grow from the middle. If s[l..r] is a palindrome and s[l-1] == s[r+1], then s[l-1..r+1] is one too. Starting from a centre and widening while the ends match checks each palindrome incrementally.
  3. Count the centres. A palindrome of odd length is centred on a letter, one of even length between two letters. That gives 2n − 1 centres: for each c try (c, c) and (c, c + 1).
  4. Keep the best. When the loop stops, l and r have each moved one step too far, so the palindrome is s[l+1:r] with length r - l - 1. Update best only if it is strictly longer.

This is the key idea: every palindrome has a centre, so expand outwards from each of the 2n − 1 centres instead of testing every substring.

The key idea

Expand around 2n − 1 centres. O(n²) time, O(1) memory.

Python solution

def longest_palindrome(s):
    best = ""
    for c in range(len(s)):
        for l, r in ((c, c), (c, c + 1)):   # odd, even
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l, r = l - 1, r + 1
            if r - l - 1 > len(best):
                best = s[l + 1:r]
    return best

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n³): n² substrings, each checked in O(n)O(n): the slice being tested
Expand around centres (shown code)O(n²): 2n − 1 centres, each expands at most n/2 times (a string like aaaa… reaches that)O(1): a few indices (plus the best answer string)

Edge cases

  • Empty string: returns "" (the loop never runs). The problem guarantees at least one character.
  • One character ("a"): returns "a".
  • No repeats ("ac"): returns "a", the first of the equal-length answers, because the update uses > not >=.
  • All the same ("aaaa"): returns "aaaa".
  • Even-length palindrome ("cbbd"): returns "bb"; only the (c, c + 1) centre finds it.
  • Several answers ("babad"): returns "bab"; "aba" is also correct and the problem accepts either.

Common mistakes

  • Trying only odd centres, which misses even palindromes: "abba" would return "a".
  • Slicing s[l:r] after the loop instead of s[l+1:r], which includes the two mismatched letters.
  • Using r - l for the length instead of r - l - 1.
  • Forgetting the bounds check l >= 0 and r < len(s), which raises an IndexError or wraps around with a negative index.
Your turn: odd lengths only

Return the longest palindromic substring whose length is odd, for example "abba" gives "a" and "forgeeksskeegfor" gives "f". Return the leftmost one if several tie. Describe your approach, then write it if you like.

Compare with our answer

Only odd palindromes have a letter as the centre, so drop the even centre and expand from each letter.

def longest_odd_palindrome(s):
    best = ""
    for c in range(len(s)):
        l = r = c
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l, r = l - 1, r + 1
        if r - l - 1 > len(best):
            best = s[l + 1:r]
    return best

longest_odd_palindrome("babad") is "bab" and longest_odd_palindrome("cbbd") is "c". Time O(n²), space O(1) besides the answer.

A strong answer mentions: using only the (c, c) centre, the same bounds check, the s[l+1:r] slice after overshooting, and that the strict > keeps the leftmost of equal answers.

Check what stuck

1. You must return the longest palindromic substring of a string of 1,000 characters, with only O(1) extra space beyond the answer. Which approach fits best?

2. Why is the expand-around-centre solution O(n²) rather than O(n)?

3. A learner deletes the even centre, so only (c, c) is tried. For which input is the answer now wrong?

Score 60% or more and the lesson is marked complete.