Shortest Palindrome by Prepending
Problem
Given a string s of lowercase letters, you may only add characters to its front. Return the shortest palindrome you can build this way. The empty string is already a palindrome, and the answer should take O(n) time.
Examples
Input: s = "abacd"
Output: "dcabacd"
Why: "aba" is already a palindrome at the front, so only "dc" is addedInput: s = "race"
Output: "ecarace"
Why: only "r" works as a palindromic front, so "eca" is addedInput: s = ""
Output: ""
Why: edge case, nothing to mirrorHints
0 / 3
Whatever you add to the front must mirror some tail of s. The less you add, the longer the part at the front of s that is already a palindrome.
So the real question is the longest prefix of s that is a palindrome. A prefix is a palindrome exactly when it equals a suffix of the reversed string, which is a question about prefixes that are also suffixes.
Build the KMP border table for s, then a separator that is not a letter, then s reversed. The border value at the very last position is the length of the longest palindromic prefix. Reverse the rest of s and put it in front.
Solution
The shortest answer keeps the longest palindromic prefix of s in the middle and adds the reverse of everything after it to the front. A prefix of s is a palindrome exactly when it also appears as a suffix of s reversed, so the longest one is the longest border of s joined to its reverse. The separator stops a border from running across the join, which would otherwise allow a match longer than s. The border table is built in linear time with the usual fall-back to shorter borders on a mismatch. Time is O(n) and space is O(n).
def shortest_palindrome(s):
t = s + "#" + s[::-1] # '#' never matches a letter
border = [0] * len(t)
for i in range(1, len(t)):
k = border[i - 1]
while k and t[i] != t[k]:
k = border[k - 1] # fall back to the border of the border
if t[i] == t[k]:
k += 1
border[i] = k
keep = border[-1] # longest palindromic prefix of s
return s[keep:][::-1] + s
print(shortest_palindrome("abacd")) # -> dcabacd
print(shortest_palindrome("race")) # -> ecarace
print(shortest_palindrome("")) # -> ""Stuck on the idea rather than the code? Build the KMP Table covers it.