169. Shortest Palindrome

HardString

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.

Examples

Input: aacecaaa

Output: aaacecaaa

Explanation: Prepend 'a' to the longest palindromic prefix 'aacecaa'.

Constraints

0 <= s.length <= 5 * 10^4
s consists of lowercase English letters only.

Run checks all cases above. Submit evaluates all test cases.