The Longest Chunked Palindrome
Split the string into consecutive pieces p1, p2, ..., pk so that p1 == pk,
p2 == pk-1, and so on. Print the largest possible k.
aabaa -> 5 a | a | b | a | a
ghiabcdefhelloadamhelloabcdefghi -> 7 ghi|abcdef|hello|adam|hello|abcdef|ghi
merchant -> 1 the whole string, which equals itself
The last line is the base case: a single piece trivially satisfies the condition, so the answer is never 0.
## The greedy
Take the shortest matching prefix and suffix, peel both off, and repeat:
lo = 0, hi = n-1, count = 0
while lo <= hi:
find the smallest k with s[lo..lo+k-1] == s[hi-k+1..hi] and 2k <= hi-lo+1
if found: count += 2; lo += k; hi -= k
else: count += 1; stop
## Why the SHORTEST match is right
Suppose the optimal split makes its first piece P of length p, and the greedy finds a
shorter matching pair of length q < p.
Because P matches the final piece, and the greedy's prefix of length q is a prefix of
P and equals the suffix of length q, the optimal split can be refined: cut P after
q characters and cut the final piece before its last q characters. That produces a
valid split with at least as many pieces, since one pair became two pairs plus whatever is
left in the middle.
So taking the shortest match never loses, and it strictly helps whenever a shorter match exists. The greedy is therefore optimal.
Taking the LONGEST match instead is wrong. On aabaa the longest matching prefix and suffix
of the whole string is aa, which peels to leave b, giving 3. The answer is 5, from
peeling a at a time.
That input is the first sample for exactly this reason.
## Why the interval DP is not the answer
The obvious alternative is dp[i][j] over the remaining middle, which is O(n^2) states
and needs a substring comparison at each, so O(n^3) without hashing.
The greedy is O(n^2) in the worst case and linear on most inputs, and it needs no table at
all. Recognising that the exchange argument holds is what saves the whole structure.
## The width guard
The matching pair must not overlap: 2k <= hi - lo + 1.
Drop it and a single leftover character matches ITSELF, getting counted as two pieces
instead of one. On aa the guard changes nothing, because the pair of length 1 satisfies
it anyway. On aaa the answer becomes 4: the outer a pair peels correctly, and then
the lone middle a is matched against itself for another 2.
So the guard is invisible on even-length inputs and wrong by exactly one pair on odd-length
ones, which is why aaa is a test.
## Boundaries
a answers 1, aa answers 2, aaa answers 3.
abab answers 2: ab matches ab, and nothing shorter does. abcabc also answers 2.
antaprezatepzapreanta answers 11, which is the long case with pieces of several
different lengths.
## Cost
Time O(n^2) in the worst case, from the inner search for the shortest match. Space
O(1).
Rolling hashes make each search O(1) amortised and the whole thing linear, which is worth
mentioning and rarely necessary.