Shortest Palindrome
Hard· KMP· palindrome
Problem
You may only add characters to the front of a string. Return the shortest palindrome you can build this way.
Examples
Input: s = "abcd"
Output: "dcbabcd"
Only "a" is a palindromic prefix, so "dcb" must be prepended.
Input: s = "aacecaaa"
Output: "aaacecaaa"
Constraints
- • 0 <= s.length <= 5 * 10^4
- • Lowercase English letters only
Hints & approach
Hint 1
The answer is determined by the longest prefix of s that is already a palindrome.
Hint 2
Everything after that prefix must be reversed and put in front.
Hint 3
Find the longest palindromic prefix in linear time using the KMP failure function on s + "#" + reverse(s).
Approachtry the hints first
Let rev be s reversed and build t = s + "#" + rev. Compute the KMP prefix-function of t; its final value is the length L of the longest prefix of s that equals a suffix of rev, which is exactly the longest palindromic prefix of s. The separator stops matches from crossing the boundary. The answer is reverse(s[L:]) + s.
Time O(n) · Space O(n)