214. Shortest Palindrome

Hard

Problem Description

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

Examples

Example 1:
Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:
Input: s = "abcd"
Output: "dcbabcd"
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def shortestPalindrome(s: str) -> str:
    if not s:
        return ""
    
    # Create string for KMP
    temp = s + "#" + s[::-1]
    
    # Build KMP table
    n = len(temp)
    lps = [0] * n
    i = 1
    length = 0
    
    while i < n:
        if temp[i] == temp[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    
    # Length of longest palindrome starting from beginning
    longest_palindrome = lps[-1]
    
    # Add reversed remaining characters to front
    return s[longest_palindrome:][::-1] + s

Alternative Solution (Brute Force):


def shortestPalindrome(s: str) -> str:
    if not s:
        return ""
    
    def is_palindrome(s: str, end: int) -> bool:
        i, j = 0, end
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True
    
    # Find longest palindrome from start
    j = len(s) - 1
    while j >= 0:
        if is_palindrome(s, j):
            break
        j -= 1
    
    # Add reversed remaining characters to front
    return s[j+1:][::-1] + s

Java Solution


class Solution {
    public String shortestPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }
        
        // Create string for KMP
        String temp = s + "#" + new StringBuilder(s).reverse().toString();
        
        // Build KMP table
        int[] lps = new int[temp.length()];
        int i = 1;
        int length = 0;
        
        while (i < temp.length()) {
            if (temp.charAt(i) == temp.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        // Length of longest palindrome starting from beginning
        int longest_palindrome = lps[temp.length() - 1];
        
        // Add reversed remaining characters to front
        return new StringBuilder(s.substring(longest_palindrome))
            .reverse()
            .append(s)
            .toString();
    }
}

C++ Solution


class Solution {
public:
    string shortestPalindrome(string s) {
        if (s.empty()) {
            return "";
        }
        
        // Create string for KMP
        string temp = s + "#" + string(s.rbegin(), s.rend());
        
        // Build KMP table
        vector lps(temp.length());
        int i = 1;
        int length = 0;
        
        while (i < temp.length()) {
            if (temp[i] == temp[length]) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        // Length of longest palindrome starting from beginning
        int longest_palindrome = lps.back();
        
        // Add reversed remaining characters to front
        return string(s.rbegin(), s.rbegin() + s.length() - longest_palindrome) + s;
    }
};

JavaScript Solution


/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function(s) {
    if (!s) {
        return "";
    }
    
    // Create string for KMP
    const temp = s + '#' + [...s].reverse().join('');
    
    // Build KMP table
    const lps = new Array(temp.length).fill(0);
    let i = 1;
    let length = 0;
    
    while (i < temp.length) {
        if (temp[i] === temp[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length !== 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    // Length of longest palindrome starting from beginning
    const longest_palindrome = lps[temp.length - 1];
    
    // Add reversed remaining characters to front
    return [...s].slice(longest_palindrome).reverse().join('') + s;
};

C# Solution


public class Solution {
    public string ShortestPalindrome(string s) {
        if (string.IsNullOrEmpty(s)) {
            return "";
        }
        
        // Create string for KMP
        string temp = s + "#" + new string(s.Reverse().ToArray());
        
        // Build KMP table
        int[] lps = new int[temp.Length];
        int i = 1;
        int length = 0;
        
        while (i < temp.Length) {
            if (temp[i] == temp[length]) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        // Length of longest palindrome starting from beginning
        int longest_palindrome = lps[temp.Length - 1];
        
        // Add reversed remaining characters to front
        return new string(s.Substring(longest_palindrome)
            .Reverse()
            .ToArray()) + s;
    }
}

Complexity Analysis

Solution Explanation

This problem can be solved using the KMP algorithm:

Key Points

Common Pitfalls

Edge Cases