Hints: Prefix-Suffix Palindrome (Hard version)

Write the required string as $t = a + b$ with $a$ a prefix of $s$ and $b$ a suffix of $s$, and $t$ a palindrome. If you delete the last $|b|$ characters of $t$, what must the remaining prefix of $t$ look like relative to $a$ and $b$?

Answer to Hint 1: The palindrome condition ties symbols on the left of $t$ to symbols on the right of $t$. Once you fix the total length of $t$ and where the cut between $a$ and $b$ sits inside $t$, the palindrome property forces a mirror relation between a tail of $a$ and a tail of $b$.

Before chasing that cut algebraically, try a structural move on $s$ itself: if the first and last characters of $s$ are equal, what can you say about how an optimal $t$ uses them?

Answer to Hint 2: While $s$ has matching ends, you can safely peel those matching pairs from both sides. Any longest answer can include all of those pairs in the outer part of the palindrome: take them from the left in $a$ and from the right in $b$. After peeling, you are left with a shorter middle string $m$ (possibly empty).

From here on, think only about building a palindrome inside $m$ as $t' = p + q$ with $p$ a prefix of $m$ and $q$ a suffix of $m$. What quantity are you maximizing?

Answer to Hint 3: You want $|t'|$ as large as possible under the prefix-or-suffix split inside $m$. The final answer for the original $s$ is: the peeled left part, then $t'$, then the peeled right part (which mirrors the peeled left part).

Invariant: after the while (l < r && s[l] == s[r]) loop, either $|m| \le 1$, or $m_0 \neq m_{|m|-1}$ (otherwise another peel would occur). If $|m| > 1$ and both $p$ and $q$ were nonempty, then the first symbol of $t'$ would be $m_0$ and the last would be $m_{|m|-1}$, impossible for a palindrome when those differ. So either $q$ is empty and $t'$ is a palindromic prefix of $m$, or $p$ is empty and $t'$ is a palindromic suffix of $m$ (equivalently $\mathrm{rev}(t')$ is a palindromic prefix of $\mathrm{rev}(m)$). Hence only two lengths matter: $|\mathrm{LPP}(m)|$ and $|\mathrm{LPP}(\mathrm{rev}(m))|$.

Caveat: hand examples on “abca” without peeling can mislead, because the program’s kmp actually runs on “bc” after removing the matching a ends.

Answer to Hint 4 (black box, first side): Build

$$ T = m + \texttt{\$} + \mathrm{rev}(m), $$

with a separator $\texttt{\$}$ outside the alphabet of $m$. Run the **prefix function** (KMP failure function) on $T$. The border length at the last position equals the length of the longest palindromic prefix of $m$.

model_sol.cpp wraps this as kmp(c) and returns that palindrome as a substring of c starting at the beginning.

Answer to Hint 5 (second side): Reverse the middle string once in memory, then call the same black box. That yields $\mathrm{LPP}(\mathrm{rev}(m))$.

If the first candidate is shorter, swap so the longer palindrome is in a, then print s.substr(0, l) + a + s.substr(r + 1).

Answer to Hint 6: If the two candidates tie in length, any choice preserves optimality.

D1 vs D2: Same reduction and same two-prefix construction; only limits differ. D1 tolerates slower scans; D2 needs linear work in $|m|$ per prefix-function pass, which is fine for the stated sum of lengths.

For the full proof with the peeled-middle invariant spelled out end-to-end, read the editorial.