#214
Shortest Palindrome
Hard KMP on s + # + reverse
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Add characters only to the front of s to make it a palindrome. Return the shortest such palindrome.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: add the fewest letters in front to make a palindrome.
Why this works: find the longest palindromic prefix: run KMP on s + "#" + reverse(s). Whatever comes after it must be mirrored in front.
Example: "aacecaaa"
longest palindromic prefix "aacecaa" (7)leftover "a" → put "a" in front → "aaacecaaa"
✦Hints open one at a time
Find the longest prefix of s that is already a palindrome.
That prefix equals a suffix of reverse(s). Build t = s + "#" + reverse(s) and compute LPS.
The '#' stops the match from running past the middle.
↗Approach
lps of t's last position = length L of the longest palindromic prefix. Prepend reverse of s[L..] to s.
</>Solution (Java)
class Solution {
public String shortestPalindrome(String s) {
String rev = new StringBuilder(s).reverse().toString();
String t = s + "#" + rev;
int[] lps = new int[t.length()];
for (int i = 1, len = 0; i < t.length(); ) {
if (t.charAt(i) == t.charAt(len)) lps[i++] = ++len;
else if (len > 0) len = lps[len - 1];
else lps[i++] = 0;
}
int keep = lps[t.length() - 1]; // longest palindromic prefix
return rev.substring(0, s.length() - keep) + s;
}
}!Common mistake
Leaving out the separator, so the LPS can be longer than s itself.
Complexity
- Time: O(n).
- Space: O(n).
Topic: String Pattern Matching
🎬 Episodes 18–19: video coming soon