All problems

Shortest Palindrome

Hard · string matching

You are given a string s of lowercase letters. You may add letters, but only at the front of s. You cannot remove letters or change the ones that are there.

Return the shortest palindrome you can make this way. A palindrome reads the same forwards and backwards.

The answer is always unique. If s is already a palindrome, return it unchanged. An empty string is a palindrome.

Examples

Example 1

Input: s = "lemon"

Output: "nomelemon"

The longest palindrome at the start of "lemon" is just "l". Add the reverse of "emon", which is "nome", in front.

Example 2

Input: s = "level"

Output: "level"

It is already a palindrome, so nothing is added.

Example 3

Input: s = "abb"

Output: "bbabb"

Only "a" is a palindrome at the start, so the other two letters are added in front, reversed.

Constraints

• 0 <= len(s) <= 10^4
• s contains only lowercase letters