Shortest Palindrome
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.
[ "aacecaaa" ]
Explanation. The string "aacecaaa" is already a palindrome. No characters need to be added.
[ "abcd" ]
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.
[ "race" ]
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.
[ "google" ]
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.
[ "madam" ]
Explanation. The string "madam" is already a palindrome. No characters need to be added.
[ "a" ]
Explanation. A single character string is always a palindrome. No characters need to be added.
[ "ab" ]
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.
[ "aaaaa" ]
Explanation. The string "aaaaa" is already a palindrome. No characters need to be added.
[ "abcde" ]
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?
* `s` consists of lowercase English letters. * `1 <= s.length <= 5 * 10^4`
- Views
- 10