Interview challenge · medium · string, dynamic-programming, expand-around-center

Longest Palindromic Substring

The challenge

Given a string s, return the longest contiguous substring of s that is a palindrome (reads the same backwards). If there are several of the same length, any one is accepted.

Example

"babad"    ->  "bab"   ("aba" is also right)
"cbbd"     ->  "bb"
"racecar"  ->  "racecar"
"a"        ->  "a"

Idea: every palindrome has a center: a character (odd length) or the gap between two characters (even length). From each of the 2n - 1 centers, grow outwards while both ends match, and keep the longest. Time O(n^2), space O(1). (Manacher's algorithm does it in O(n), but this is the one asked for in interviews.)

The solution

1# Longest Palindromic Substring - ayotl.dev
2def grow(s, lo, hi):
3    # expand while both ends match
4    while lo >= 0 and hi < len(s):
5        if s[lo] != s[hi]:
6            break
7        lo, hi = lo - 1, hi + 1
8    return s[lo + 1:hi]
9
10
11def longest_pal(s):
12    best = ""
13    for i in range(len(s)):
14        # odd center, then even center
15        for p in (grow(s, i, i),
16                  grow(s, i, i + 1)):
17            if len(p) > len(best):
18                best = p
19    return best
20
21
22for s in ["babad", "cbbd", "racecar", "a"]:
23    print(s, "->", longest_pal(s))

$ python3 longest_palindromic_substring.py

babad -> bab

cbbd -> bb

racecar -> racecar

a -> a

The video

Watch on YouTube →