DSA Longest Palindromic Substring

The problem

A palindrome is a string that reads the same forwards and backwards. A substring is a run of neighbouring letters inside a string. The problem asks for the longest substring that is a palindrome.

When two substrings tie for the longest length, this article keeps the first one found. The input may be empty.

cases = [
    ("babad", "bab"),
    ("cbbd", "bb"),
    ("forgeeksskeegfor", "geeksskeeg"),
    ("aaaa", "aaaa"),
    ("ac", "a"),
]
for text, expected in cases:
    print("text", text, "-> longest palindrome:", expected)

The first case holds two palindromes of length 3, bab and aba. The tie rule keeps bab, the one that starts earlier. The second case holds an even-length answer, and that shape drives the whole method.

Intuition: centres on letters only

A palindrome mirrors around its middle. Growing outward from a middle letter finds odd-length palindromes. A first attempt tries exactly that, one expansion per letter.

def expand(text, left, right):
    while left >= 0 and right < len(text) and text[left] == text[right]:
        left -= 1
        right += 1
    return right - left - 1, left + 1

text = "cbbd"
best = ""
for centre in range(len(text)):
    length, start = expand(text, centre, centre)
    if length > len(best):
        best = text[start:start + length]
print("best found:", best)
print("its length:", len(best))
print("the true longest is bb, length 2")

The attempt answers with a single letter. The palindrome bb mirrors around the gap between the two b letters, not around a letter. Even-length palindromes have no middle letter, so letter centres can never grow them.

Brute force: test every substring

The brute force cuts out every substring and tests each one against its reverse. It keeps the longest palindrome found. A counter records the substrings tested.

def brute(text):
    best = ""
    checked = 0
    for i in range(len(text)):
        for j in range(i + 1, len(text) + 1):
            piece = text[i:j]
            checked += 1
            if piece == piece[::-1] and len(piece) > len(best):
                best = piece
    return best, checked

for text in ["babad", "cbbd", "aaaa"]:
    best, checked = brute(text)
    print(text, "-> longest:", best, "substrings checked:", checked)

The answers agree with the cases from section 1. The cost is the test count, and each test itself scans the substring. Longer strings make both factors grow.

The optimal solution: expand around every centre

The state is the best start and best length seen so far. Every centre is tried in two forms, on a letter for odd lengths and in the gap after it for even lengths, and each expansion grows while the two outer letters match.

A string of length n has 2n minus 1 centres in this scheme. Each expansion stops at the first mismatch or at the string's edge. Only a strictly longer result replaces the stored best, which is what keeps the first of a tie.

def longest_palindrome(text):
    def expand(left, right):
        while left >= 0 and right < len(text) and text[left] == text[right]:
            left -= 1
            right += 1
        return right - left - 1, left + 1

    best_length = 0
    best_start = 0
    for centre in range(len(text)):
        for left, right in [(centre, centre), (centre, centre + 1)]:
            length, start = expand(left, right)
            if length > best_length:
                best_length = length
                best_start = start
    return text[best_start:best_start + best_length]

cases = [
    ("babad", "bab"),
    ("cbbd", "bb"),
    ("forgeeksskeegfor", "geeksskeeg"),
    ("aaaa", "aaaa"),
    ("ac", "a"),
]
for text, expected in cases:
    result = longest_palindrome(text)
    print(text, "->", result, "expected:", expected, "match:", result == expected)

All five cases match, including the even-length bb and the whole-string aaaa. Storing a start and a length avoids building every candidate substring.

Walkthrough: every centre in babad

The walk tries all nine centres of babad in order. Each line prints the centre, the longest palindrome around it, and the best after that centre. The answer is read off the last line.

def expand(text, left, right):
    while left >= 0 and right < len(text) and text[left] == text[right]:
        left -= 1
        right += 1
    return right - left - 1, left + 1

text = "babad"
best = ""
for centre in range(len(text)):
    for kind, left, right in [("letter", centre, centre), ("gap", centre, centre + 1)]:
        length, start = expand(text, left, right)
        piece = text[start:start + length]
        if length > len(best):
            best = piece
        print("centre", centre, kind, "- longest here:", piece if piece else "-", "- best so far:", best)
print("answer:", best)

Centre 1, the letter a, grows to bab and takes the lead. Centre 2 grows to aba, the same length, and the tie rule leaves bab in front. No later centre grows past length 1.

Complexity

Expansion costs O(n squared) time in the worst case, since each of the 2n minus 1 centres can grow across the string. It stores only a start and a length, so its extra space is O(1).

The brute force tests each substring with a scan of its own, which makes its total work grow with the cube of the length. The counter below counts letter comparisons for the brute force and successful expansion steps for the walk, on strings of one repeated letter, where both do their most work.

def brute_comparisons(text):
    total = 0
    for i in range(len(text)):
        for j in range(i + 1, len(text) + 1):
            left, right = i, j - 1
            while left < right:
                total += 1
                if text[left] != text[right]:
                    break
                left += 1
                right -= 1
    return total

def expansion_steps(text):
    steps = 0
    for centre in range(len(text)):
        for left, right in [(centre, centre), (centre, centre + 1)]:
            while left >= 0 and right < len(text) and text[left] == text[right]:
                steps += 1
                left -= 1
                right += 1
    return steps

for n in [4, 8, 12]:
    text = "a" * n
    print("length", n, "- brute comparisons:", brute_comparisons(text), " expansion steps:", expansion_steps(text))

At length 4 the counts are still close, 7 against 10. From length 8 on, the brute count pulls away, 50 against 36 and then 161 against 78. Both methods agree on the answer; only the work differs.

Edge cases and pitfalls

An empty string answers with an empty string. A single letter answers with itself. A string with no repeated neighbours answers with its first letter, by the tie rule.

def longest_palindrome(text):
    def expand(left, right):
        while left >= 0 and right < len(text) and text[left] == text[right]:
            left -= 1
            right += 1
        return right - left - 1, left + 1

    best_length = 0
    best_start = 0
    for centre in range(len(text)):
        for left, right in [(centre, centre), (centre, centre + 1)]:
            length, start = expand(left, right)
            if length > best_length:
                best_length = length
                best_start = start
    return text[best_start:best_start + best_length]

for text in ["", "a", "ac", "aaaa", "bb", "babad"]:
    print(repr(text), "->", repr(longest_palindrome(text)))

The gap centres are the pitfall. Dropping them, as the intuition section did, loses every even-length palindrome. The centre list must carry both forms for every letter.