Shortest Palindrome

mediumSave

StringString Matching

Given a string s, you can transform it into a palindrome by inserting characters in front of it. Find the shortest palindrome you can form by doing this.

For example:

Example 1: Input: s = "aacecaaa" Output: "aaacecaaa" Explanation: The string is already a palindrome, so no characters need to be added.

Example 2: Input: s = "abcd" Output: "dcbabcd" Explanation: The longest palindromic prefix of "abcd" is "a". The remaining suffix is "bcd". Reversing "bcd" gives "dcb". Prepending "dcb" to "abcd" forms "dcbabcd", which is the shortest palindrome.

Example 1

Input

[
  "aacecaaa"
]

Output

aaacecaaa

Explanation. The string "aacecaaa" is already a palindrome. No characters need to be added.

Example 2

Input

[
  "abcd"
]

Output

dcbabcd

Explanation. The longest palindromic prefix of "abcd" is "a". The remaining suffix is "bcd". Reversing "bcd" gives "dcb". Prepending "dcb" to "abcd" forms "dcbabcd", which is the shortest palindrome.

Example 3

Input

[
  "race"
]

Output

ecarace

Explanation. The longest palindromic prefix of "race" is "r". The remaining suffix is "ace". Reversing "ace" gives "eca". Prepending "eca" to "race" forms "ecarace", which is the shortest palindrome.

Example 4

Input

[
  "google"
]

Output

elgoogle

Explanation. The longest palindromic prefix of "google" is "g". The remaining suffix is "oogle". Reversing "oogle" gives "elgoo". Prepending "elgoo" to "google" forms "elgoogle", which is the shortest palindrome.

Example 5

Input

[
  "madam"
]

Output

madam

Explanation. The string "madam" is already a palindrome. No characters need to be added.

Example 6

Input

[
  "a"
]

Output

Explanation. A single character string is always a palindrome. No characters need to be added.

Example 7

Input

[
  "ab"
]

Output

bab

Explanation. The longest palindromic prefix of "ab" is "a". The remaining suffix is "b". Reversing "b" gives "b". Prepending "b" to "ab" forms "bab", which is the shortest palindrome.

Example 8

Input

[
  "aaaaa"
]

Output

aaaaa

Explanation. The string "aaaaa" is already a palindrome. No characters need to be added.

Example 9

Input

[
  "abcde"
]

Output

edcbabcde

Explanation. The longest palindromic prefix of "abcde" is "a". The remaining suffix is "bcde". Reversing "bcde" gives "edcb". Prepending "edcb" to "abcde" forms "edcbabcde", which is the shortest palindrome.

Follow-up: Can you solve this with an approach that leverages string hashing or a KMP-like precomputation (e.g., using its LPS array) for optimal efficiency?

Constraints:

* `s` consists of lowercase English letters. * `1 <= s.length <= 5 * 10^4`

Views: 4