Palindromes

Big idea

A palindrome reads the same both ways, so compare from the outside in: two indices start at the ends and walk toward each other. To find palindromes inside a string, flip it around — expand outward from each possible centre, which finds all of them in O(n²) with O(1) space.

Checking one string

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

n/2 comparisons, no copies. s == s[::-1] is also O(n) but builds a reversed copy.

Real problems add noise. "A man, a plan, a canal: Panama" is a palindrome if you skip non-alphanumeric characters and ignore case:

def is_clean_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if not s[i].isalnum():
            i += 1
        elif not s[j].isalnum():
            j -= 1
        elif s[i].lower() != s[j].lower():
            return False
        else:
            i, j = i + 1, j - 1
    return True

One deletion allowed

"Valid Palindrome II" lets you delete at most one character. Walk inward as usual; at the first mismatch you have exactly two options — skip the left character or skip the right one — and each is a plain palindrome check on what's left:

def is_pal(s, i, j):
    while i < j:
        if s[i] != s[j]:
            return False
        i, j = i + 1, j - 1
    return True

def valid_with_one_delete(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return is_pal(s, i + 1, j) or is_pal(s, i, j - 1)
        i, j = i + 1, j - 1
    return True

O(n): the main walk plus at most two more.

Finding palindromes: expand around the centre

Every palindrome has a centre. In a string of length n there are 2n − 1 centres: each character (odd lengths, like "aba") and each gap between neighbours (even lengths, like "abba"). From a centre, expand while the two ends match:

def expand(s, lo, hi):
    while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
        lo -= 1
        hi += 1
    return lo + 1, hi        # s[lo+1:hi] is the palindrome

def longest_palindrome(s):
    best = (0, 0)
    for c in range(len(s)):
        for lo, hi in (expand(s, c, c), expand(s, c, c + 1)):
            if hi - lo > best[1] - best[0]:
                best = (lo, hi)
    return s[best[0]:best[1]]

Each expansion is O(n) at worst and there are 2n − 1 centres, so O(n²) time and O(1) space. Counting all palindromic substrings is the same loop: add one for every successful expansion step.

A dynamic programming table (pal[i][j] = is s[i..j] a palindrome) also works in O(n²) but uses O(n²) memory. Manacher's algorithm does it in O(n); it's rarely expected in interviews.

Watch it

Expand around both kinds of centre in xabbay.

Practice

• Valid Palindrome
• Valid Palindrome II
• Longest Palindromic Substring
• Palindromic Substrings

Quick check