hardMath / GeometryPure DSA~45 min
Shortest Prefix Pad To Palindrome
A symmetric key must be a palindrome. Given a seed string, prepend the fewest characters in front of it so the whole result reads the same both ways.
Problem
Given a string s, prepend the minimum number of characters to its front to make it a palindrome, and return the resulting shortest palindrome.
Input
A string s (0 ≤ |s| ≤ 5·10^4) of lowercase letters.
Output
The shortest palindrome formed by prepending characters to s.
Constraints
- 0 ≤ |s| ≤ 5·10^4
- Characters may only be added at the front
- Target O(n) time
Examples
Example 1
Input
s = "aacecaaa"
Output
"aaacecaaa"
Prepending one 'a' makes the whole string a palindrome.
Example 2
Input
s = "abcd"
Output
"dcbabcd"
The longest palindromic prefix is 'a'; prepend 'dcb'.