Add the fewest characters in front of a string so the whole string becomes a palindrome.
Problem
Given a string s, construct the shortest palindrome by adding characters only to the front of s.
Your task is to return the resulting palindrome string with the minimum possible number of added characters.
A palindrome reads the same forward and backward.
Goal
Find the shortest string of the form:
prefix + s
where prefix is added in front of s, and the entire result is a palindrome.
Input Format
- A single string
s. - The string contains lowercase English letters unless otherwise specified by the platform.
Output Format
- Return the shortest palindrome formed by adding characters only to the front of
s.
Constraints
1 <= |s| <= $10^{5}$is a reasonable interview-scale assumption.- The answer must be a palindrome.
- Only front insertions are allowed.
Example 1
Input
s = "aacecaaa"
Output
"aaacecaaa"
Explanation
The prefix "aacecaa" is already a palindrome, so only one character needs to be added to the front.
Example 2
Input
s = "abcd"
Output
"dcbabcd"
Explanation
The longest palindromic prefix is "a". Adding the reverse of the remaining suffix "bcd" gives "dcbabcd".
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.