Loading problem…
You are given a string s. You can convert s to a palindrome by adding characters in front of it. Return the shortest palindrome you can find by performing this transformation.
Example 1
Input: s = aacecaaa
Output: aaacecaaa
Explanation: The longest prefix of s that is already a palindrome is "aacecaa". Only the final 'a' is left over, so adding one 'a' to the front gives "aaacecaaa".
Example 2
Input: s = abcd
Output: dcbabcd
Explanation: Only "a" is a palindromic prefix of "abcd". The rest, "bcd", reversed as "dcb", is added to the front, giving "dcbabcd".
Example 3
Input: s = a
Output: a
Explanation: "a" is already a palindrome, so nothing needs to be added.
The characters we must prepend are the reverse of the part of s that is NOT already a palindromic prefix. Find the longest palindromic prefix in O(n) with a KMP failure function over s + '#' + reverse(s).
Run checks all cases above. Submit evaluates all test cases.