Shortest Palindrome

Share

Add characters to the front of s to make it a palindrome. Return shortest result.

Example 1
Input: s="aacecaaa" → Output: "aaacecaaa"
Example 2
Input: s="abcd" → Output: "dcbabcd"

Solution Approach

Use KMP to find the longest palindrome prefix. Append reverse of remaining suffix to front.

  • Construct string: s + "#" + reverse(s)
  • Apply KMP failure function to this combined string
  • Last value of lps = length of longest palindrome prefix
  • Add reverse of s[lps..] to the front of s
Java
public String shortestPalindrome(String s) {
    String rev = new StringBuilder(s).reverse().toString();
    String combined = s + "#" + rev;
    int n = combined.length();
    int[] lps = new int[n];
    for (int i = 1, len = 0; i < n; ) {
        if (combined.charAt(i) == combined.charAt(len)) lps[i++] = ++len;
        else if (len > 0) len = lps[len-1];
        else lps[i++] = 0;
    }
    int longest = lps[n-1];
    return rev.substring(0, s.length() - longest) + s;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)