528. 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.

Constraints - `1 ≤ length of s ≤ 2000` - `s` contains only lowercase letters