214. Shortest Palindrome

Description

The problem requires us to find the shortest palindrome that can be formed by adding characters in front of a given string. A palindrome is a string that reads the same forwards and backwards.

Intuition

A simple observation is that the longest palindromic prefix of the given string should remain unchanged, and the characters that follow this prefix must be reversed and added to the start of the string to make it a palindrome. Thus, the task is reduced to finding the longest palindromic prefix.

Approach

1. Reverse the input string and concatenate it with the original string, separated by a unique delimiter (#) to avoid false matches.
2. Use the KMP (Knuth-Morris-Pratt) algorithm to compute the longest palindromic prefix by building the LPS (Longest Prefix Suffix) array on the concatenated string.
3. The length of the longest palindromic prefix can be found at the last index of the LPS array.
4. Using this length, the remaining part of the reversed string is added to the front of the original string to form the shortest palindrome.

Complexity

Time Complexity:

O(n), where n is the length of the input string. This is because we compute the LPS array in linear time using the KMP algorithm.

Space Complexity:

O(n) due to the storage of the LPS array and the concatenated string.

Code

C++

class Solution {
public:
    string shortestPalindrome(string s) {
        string rev_s = s;
        reverse(rev_s.begin(), rev_s.end());
        
        // Create a new string with a delimiter between s and its reverse.
        string new_s = s + "#" + rev_s;

        // Create the LPS (longest prefix suffix) array
        vector lps(new_s.length(), 0);
        
        // Build the LPS array for KMP algorithm
        for (int i = 1; i < new_s.length(); i++) {
            int j = lps[i - 1];
            while (j > 0 && new_s[i] != new_s[j]) {
                j = lps[j - 1];
            }
            if (new_s[i] == new_s[j]) {
                j++;
            }
            lps[i] = j;
        }

        // Length of the longest palindromic prefix
        int palin_len = lps[new_s.length() - 1];
        
        // Add the remaining part of the reversed string to the front
        return rev_s.substr(0, s.length() - palin_len) + s;
    }
};

Python

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        palindromeStr = s[::-1]
        
        if s == palindromeStr:
            return s

        for i in range(len(s)):
            if s[:len(s) - i] == palindromeStr[i:]:
                return palindromeStr[:i] + s

        return ""

Java

class Solution {
    public String shortestPalindrome(String s) {
        StringBuilder palindromeStr = new StringBuilder(s).reverse();
        
        if (s.equals(palindromeStr.toString())) {
            return s;
        }

        for (int i = 0; i < s.length(); i++) {
            if (s.substring(0, s.length() - i).equals(palindromeStr.substring(i))) {
                return palindromeStr.substring(0, i) + s;
            }
        }

        return "";
    }
}

JavaScript

var shortestPalindrome = function (s) {
    const palindromeStr = s.split("").reverse().join("");
    
    if (s === palindromeStr) {
        return s;
    }

    for (let i = 0; i < s.length; i++) {

        if (s.substring(0, s.length - i) === palindromeStr.substring(i)) {
            return palindromeStr.substring(0, i) + s;
        }
    }
    return "";
};