O(n) O(n)
Intuition
The characters we must prepend are the reverse of the part of s that is NOT already a palindromic prefix. Find the longest palindromic prefix in O(n) with a KMP failure function over s + '#' + reverse(s).
Explanation
Longest palindromic prefix
The shortest palindrome prepends the reverse of the suffix that lies beyond the longest palindromic prefix of s. To find that prefix length in linear time, build the string combined = s + '#' + reverse(s) and compute its KMP failure function; the last value lps[-1] is exactly the longest palindromic prefix length.
combined = s + '#' + s[::-1]
lps = kmp_failure(combined)
longest = lps[-1]
return s[::-1][: len(s)-longest] + s
The # separator prevents overlap between the two halves.
Worked example
"aacecaaa" → longest palindromic prefix "aacecaa" (7), prepend "a" → "aaacecaaa".
Complexity
- Time: O(n).
- Space: O(n).
Implementation
class Solution {
public String shortestPalindrome(String s) {
if (s.isEmpty()) return s;
String rev = new StringBuilder(s).reverse().toString();
String combined = s + "#" + rev;
int m = combined.length();
int[] lps = new int[m];
for (int i = 1; i < m; i++) {
int j = lps[i - 1];
while (j > 0 && combined.charAt(i) != combined.charAt(j)) j = lps[j - 1];
if (combined.charAt(i) == combined.charAt(j)) j++;
lps[i] = j;
}
int longest = lps[m - 1];
return rev.substring(0, s.length() - longest) + s;
}
}