214. Shortest Palindrome

Time: O(n)

Space: O(n)

Intuition

Find the longest palindromic prefix of s. The shortest palindrome is formed by appending the reverse of the non-palindromic suffix. Use KMP failure function on s + "#" + reverse(s) to find the longest prefix of s that matches a suffix of reverse(s) - that's the longest palindromic prefix.

Algorithm

1rev = reverse of s.
2Compute KMP failure function for combined = s + "#" + rev.
3The failure value at the last position tells us the length of the longest palindromic prefix of s.
4Prefix = s[0..lps-1] (palindrome). Suffix = s[lps..] (non-palindromic remainder).
5Return reverse(suffix) + s.

Example Walkthrough

Input: s = "aacecaaa"

1.combined = "aacecaaa#aaacecaa".
2.KMP lps at end = 7. Longest palindromic prefix = "aacecaa" (length 7).
3.Remaining suffix = "a". Reverse = "a". Return "a" + "aacecaaa" = "aaacecaaa".

Output: "aaacecaaa"

Common Pitfalls

•The "#" separator is critical - prevents the KMP from matching across the boundary between s and rev.

214.cs

// Approach: Find the longest palindromic prefix of s using KMP / rolling hash.
// Construct the string s + '#' + reverse(s) and compute the KMP failure function.
// The last value of the failure function gives the length of the longest palindromic prefix.
// Prepend the reverse of the remaining suffix (s[prefixLen..]) to s to form the shortest palindrome.
// Rolling hash implementation: compare hash of prefix from left and from right simultaneously.
// Time: O(n) Space: O(n) for the reversed string and hash computation.

public class Solution
{
    public string ShortestPalindrome(string s)
    {
        // we use a prime number as a base for computing rolling hash
        const int baseValue = 131;
        int multiplier = 1;  // modular multiplication factor, initially 1
        const int mod = (int)1e9 + 7; // we will use a large prime number to mod the result to avoid overflow
        int prefixHash = 0; // rolling hash from the front
        int suffixHash = 0; // rolling hash from the back
        int palindromeIdx = 0; // the index till the string is a palindrome     
        int length = s.Length; // length of the string

        // iterate through the string to update the prefix and suffix hashes
        for (int i = 0; i < length; ++i)
        {
            // convert character to number (assuming lowercase 'a' to 'z')
            int charValue = s[i] - 'a' + 1;
            // update the prefix hash and ensure it is within the bounds by taking modulo
            prefixHash = (int)(((long)prefixHash * baseValue + charValue) % mod);
            // update the suffix hash and ensure it is within the bounds by taking modulo
            suffixHash = (int)((suffixHash + (long)charValue * multiplier) % mod);
            // update the multiplier for the next character
            multiplier = (int)(((long)multiplier * baseValue) % mod);

            // if the prefix and suffix are equal, then we know the string up to index i is a palindrome
            if (prefixHash == suffixHash)
                palindromeIdx = i + 1;
        }

        // If the whole string is a palindrome, return it as is
        if (palindromeIdx == length)
            return s;

        // We need to add the reverse of the substring from palindromeIdx to the end to the front
        // to make the string a palindrome
        string suffixToBeAdded = new string(s.Substring(palindromeIdx).ToCharArray().Reverse().ToArray());

        // Return the string with the suffix added in front to form the shortest palindrome
        return suffixToBeAdded + s;
    }
}

Was this solution helpful?