Problem statement

https://leetcode.com/problems/shortest-palindrome/

Solution

Basically, we need to find the longest prefix, which is palindrome. Create string s + "!" + s[::-1], and then we need to calculate the prefix function for this new string, namely, the value for the last element. See also problem 1392.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def shortestPalindrome(self, s):
        def prefix(s):
            p = [0] * len(s)
            for i in range(1, len(s)):
                k = p[i - 1]
                while k > 0 and s[k] != s[i]:
                    k = p[k - 1]
                if s[k] == s[i]:
                    k += 1
                p[i] = k
            return p
        
        max_index = prefix(s + "!" + s[::-1])[-1]
        return s[:max_index-1:-1] + s

Remark

Another way to solve this problem in O(n) (in average) is to use rolling hash.