Shortest Palindrome
HardFind the longest palindromic prefix with KMP
Problem
Return the shortest palindrome formed by adding characters only in front of the given string.
Find the longest palindrome starting at the front, then mirror the rest onto the front.
The idea
You may only prepend characters, so the part of the string already forming a palindrome from the start must be preserved. Running the LPS construction on s + '#' + reverse(s) gives the length of that longest palindromic prefix; reverse and prepend the rest.
The trick
- The separator '#' stops the match spilling across the two halves.
- Prepend reverse(s.substring(lpsValue)).
- O(n) with KMP; the naive check is O(n²).
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — aacecaaa Values: 0.
1combine = s + '#' + reverse(s)2lps = kmp(combine); k = lps[last]3return reverse(s[k:]) + sInput
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "aacecaaa"
- Output:
- "aaacecaaa"
- Explanation:
- Add one char in front to mirror it.
Example 2
- Input:
- s = "abcd"
- Output:
- "dcbabcd"
- Explanation:
- Prepend dcb → dcbabcd.
Example 3
- Input:
- s = "aba"
- Output:
- "aba"
- Explanation:
- Already a palindrome.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.