The Longest Palindromic Substring
Print the LENGTH of the longest contiguous substring that reads the same forwards and backwards.
babad -> 3 bab, or aba
cbbd -> 2 bb
forgeeksskeegfor -> 10 geeksskeeg
Problem #423 asks for the longest palindromic SUBSEQUENCE, where characters may be skipped. Contiguity changes the method completely, and this is worth seeing side by side: the subsequence version genuinely needs a table over substrings, and this one does not.
## The table version, and why it is not the best answer
pal[i][j] = is s[i..j] a palindrome
pal[i][j] = (s[i] == s[j]) and (j - i < 2 or pal[i+1][j-1])
Filled by increasing length, that is O(n^2) time and O(n^2) SPACE, and the space is
what hurts: at n = 5000 it is 25 million entries.
## Expanding around a centre
Every palindrome has a centre. There are 2n - 1 of them, n single characters and
n - 1 gaps between adjacent characters, and from each one the palindrome can be grown
outward while the two ends agree:
for each centre:
lo, hi = the centre
while lo >= 0 and hi < n and s[lo] == s[hi]:
record hi - lo + 1
lo -= 1; hi += 1
Same O(n^2) time, O(1) space, and considerably less code.
The observation that buys it is that the table stores one bit per substring while the question only needs the best length, so the substrings never have to be remembered, only walked.
## Both kinds of centre
Odd-length palindromes have a character at the centre and even-length ones have a gap.
Handling only one kind is the standard bug and it is silent: cbbd answers 1 instead of
2 with only odd centres, and racecar answers 0 or 1 with only even ones.
Both inputs are tests, in both directions, because a solution that forgets one kind still returns a plausible number.
## Boundaries
A single character is a palindrome, so the answer is at least 1 for any non-empty string.
abcda answers 1: the two as are not adjacent, so no palindrome longer than one exists
even though the first and last characters agree.
That input is the check on not confusing substring with subsequence, where aa would be
available.
## Cost
Time O(n^2). Space O(1).
There is an O(n) algorithm, Manacher's, which is worth knowing exists and is rarely the
expected answer.