Shortest Palindrome

Problem

Return the shortest palindrome that can be formed by adding characters only to the front of s.

Find the longest palindromic prefix of s with the KMP prefix function on s plus a separator plus the reverse of s, then prepend the reversed leftover suffix. An empty or single-character string is already a palindrome.

Hint

The last value of the KMP table on s + separator + reverse(s) is the longest palindromic prefix length.

Test cases

case 1

in: ["aacecaaa"]

expected: "aaacecaaa"

case 2

in: ["abcd"]

expected: "dcbabcd"

case 3

in: [""]

expected: ""

case 4

in: ["a"]

expected: "a"

case 5

in: ["aba"]

expected: "aba"

Starter codePython

def shortest_palindrome(s):
    # Your code here
    pass

5 test cases · run your code against them in the editor