DiffPush Tier Strings Hard · Hard O(n) · O(n)
A security firm stamps access badges with codes that must read as palindromes, but legacy badges fail the check. The forging machine may only prepend characters — the existing code stays untouched at the end. The badge system computes the shortest prependable patch that turns each legacy code into a palindrome.
Input: A string s.
Output: Return the shortest palindrome obtainable by adding characters only in front of s.
0 <= len(s) <= 5 * 10^4s consists of lowercase English lettersInput: {"s":"aacecaaa"}
Output: "aaacecaaa"
Prepending one 'a' completes the palindrome; the longest palindromic head of s spans "aacecaa".
Input: {"s":"abcd"}
Output: "dcbabcd"
The longest palindromic head is just "a", so the remaining "bcd" reversed goes in front.