Skills101
← All coding problems

Shortest Palindrome by Adding in Front

hardStrings II+40 XPTime limit 2s

You may add characters only at the front of a string. Make it a palindrome using as few added characters as possible, and print the resulting palindrome. aacecaaa becomes aaacecaaa (one a added), and abcd becomes dcbabcd.

Input: one line with a string of lowercase letters.

Output: the shortest palindrome that ends with the given string.

Constraints: 1 ≤ length ≤ 10⁵.

Think about it: you keep the longest prefix that is already a palindrome, and add the reverse of the rest in front. Testing each prefix is O(n²). Instead build s + '#' + reverse(s) and compute its prefix function: the last value is exactly the length of the longest palindromic prefix (it is a prefix of s that equals a suffix of reverse(s)).

Sample input 1

aacecaaa

Sample output 1

aaacecaaa

Sample input 2

abcd

Sample output 2

dcbabcd

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.