4.23.5 — Longest Palindromic Substring

LeetCode 5 · Medium · ★ Blind 75

The problem

Return the longest substring of s that reads the same forwards and backwards.

"babad"  →  "bab"   (or "aba" — either is accepted)
"cbbd"   →  "bb"

Up to 1,000 characters.

The pattern

Every palindrome has a centre. So instead of checking every substring, stand at each possible centre and push outwards while the characters match.

The catch is that there are two kinds of centre:

• Odd length — a single character, like the a in "bab".
• Even length — the gap between two characters, like between the two bs in "bb".

A string of n characters has n character-centres and n − 1 gap-centres, so 2n − 1 in total. Try them all.

Forgetting the even case is the most common bug in this problem, and it fails on "cbbd" — the answer "bb" has no middle character.

The solution

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        best_start, best_len = 0, 0

        def expand(lo: int, hi: int):
            nonlocal best_start, best_len
            while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
                lo -= 1
                hi += 1
            # the loop overshot by one on each side
            length = hi - lo - 1
            if length > best_len:
                best_len = length
                best_start = lo + 1

        for i in range(len(s)):
            expand(i, i)          # odd centre: one character
            expand(i, i + 1)      # even centre: the gap after it

        return s[best_start:best_start + best_len]

TypeScript

function longestPalindrome(s: string): string {
  let bestStart = 0, bestLen = 0;

  function expand(lo: number, hi: number): void {
    while (lo >= 0 && hi < s.length && s[lo] === s[hi]) { lo--; hi++; }
    const len = hi - lo - 1;
    if (len > bestLen) { bestLen = len; bestStart = lo + 1; }
  }

  for (let i = 0; i < s.length; i++) {
    expand(i, i);
    expand(i, i + 1);
  }

  return s.slice(bestStart, bestStart + bestLen);
}

The off-by-one after the loop is the fiddly part, so derive it rather than guess. The while stops when the characters no longer match, which means lo and hi have each moved one step too far. The palindrome actually spans lo + 1 to hi - 1, and its length is (hi - 1) - (lo + 1) + 1 = hi - lo - 1.

expand(i, i + 1) handles the even case, and it needs no bounds check — if i + 1 is past the end, the while condition fails immediately and the length comes out as 0.

Track indices, not substrings. Slicing inside the loop would be O(n) per check and would make the whole thing O(n^3). This is the same discipline as 4.6.5.

Complexity

O(n^2) time — 2n − 1 centres, each expanding up to n/2 steps.

O(1) space, which is the real advantage over the DP version below.

The DP version, and why it is worse here

This problem is filed under dynamic programming, so here is the DP, and here is why you should not write it.

Let dp[i][j] be true when s[i..j] is a palindrome:

dp[i][j] = (s[i] = s[j]) \ \text{and}\ \big(j - i < 2 \ \text{or}\ dp[i+1][j-1]\big)

The ends match, and the inside is already known to be a palindrome. The j - i < 2 covers lengths 1 and 2, which have no inside.

n = len(s)
dp = [[False] * n for _ in range(n)]
best = (0, 1)
for j in range(n):
    for i in range(j, -1, -1):                    # i counts DOWN
        if s[i] == s[j] and (j - i < 2 or dp[i+1][j-1]):
            dp[i][j] = True
            if j - i + 1 > best[1]:
                best = (i, j - i + 1)
return s[best[0]:best[0] + best[1]]

The loop order is the whole difficulty. dp[i][j] reads dp[i+1][j-1] — a larger i and a smaller j — so i must count downwards while j counts upwards, or you read cells that are not filled yet. That ordering question is the thing 2-D DP is really about, and it is covered properly in 4.24.

O(n^2) time and O(n^2) space.

Same time, far more memory, more code, and an ordering trap. Centre expansion wins on every count. Write it, and mention the DP as the version that generalises — because the table is genuinely useful in 4.18.7 Palindrome Partitioning, where you need to test many substrings rather than find one.

That is the real lesson: precompute a table when you will query it repeatedly; expand from centres when you need one answer.

Manacher's algorithm

There is an O(n) solution. It runs centre expansion but reuses information from palindromes already found, so a centre inside a known palindrome starts from a lower bound instead of from zero — the same "the pointer only moves forward" argument as the sliding window and the monotonic stack.

It is intricate and almost never expected. Name it, say it is O(n), and move on. 4.31 builds it properly.

Where this goes next

• Palindromic Substrings — count them all instead of finding the longest. The identical expansion with a counter. 4.23.6.
• Longest Palindromic Subsequence — a completely different problem, because gaps are allowed. It is genuinely 2-D DP, and it equals the longest common subsequence of the string and its reverse. 4.24.
• Palindrome Partitioning II — the fewest cuts, which needs the DP table.

Substring means contiguous; subsequence allows gaps. Confusing them changes the algorithm completely, and it is worth reading the problem statement twice.

What the interviewer will push on

"How many centres are there?" 2n − 1. Explain the even case, and say what "cbbd" does to a solution that misses it.

"Derive the length after expansion." The loop overshoots by one on each side, so it is hi - lo - 1.

"Can you do better than O(n^2)?" Manacher's, O(n). Naming it is enough.

"Why not DP?" Same time, O(n^2) space instead of O(1), and a loop-order trap. Then say when the table is worth building.

"What about the longest palindromic subsequence?" Different problem — 2-D DP, and it is LCS with the reversed string.

One thing to volunteer: say the centre count and the even-centre case before writing anything. It is the one place this problem is designed to catch you.

Next: 4.23.6 Palindromic Substrings — the same expansion, counting instead of measuring.