Shortest Palindrome

You may add letters only in front of s. Return the shortest palindrome you can get this way.

For "aacecaaa" the answer is "aaacecaaa"; for "abcd" it is "dcbabcd".

The starter code tests every prefix for being a palindrome letter by letter. It is correct but too slow for long strings.

Examples

Example 1

Input:

shortest_palindrome('aacecaaa')

Output:

'aaacecaaa'

Example 2

Input:

shortest_palindrome('abcd')

Output:

'dcbabcd'

Constraints

• 0 <= len(s) <= 200000
• Lower-case letters.