We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Palindrome

Difficulty: 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.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • The goal is to find the shortest prefix of the original string to prepend, making the entire string a palindrome.
  • The longest palindromic suffix of the string can help determine the minimal characters needed to be added in front.
  • Efficiently identifying the longest palindromic suffix can be done using string matching techniques.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(n)

Solution

To solve the problem, we can utilize the concept of string matching to find the longest palindromic suffix. The steps are as follows:

  1. Reverse the input string and concatenate it with the original string, separated by a special character that does not appear in the string (to avoid overlap).
  2. Compute the longest prefix which is also a suffix using KMP (Knuth-Morris-Pratt) algorithm techniques on this concatenated string.
  3. The longest palindromic suffix can be derived from the length of this prefix.
  4. The characters needed to add in front of the original string are the characters from the start of the reversed string that do not match this suffix.

This approach efficiently determines the shortest palindrome by leveraging the properties of string matching.

Code Solutions

def shortestPalindrome(s: str) -> str:
    if not s:
        return s
    
    # Reverse the string
    rev_s = s[::-1]
    # Create a new string for KMP
    new_s = s + "#" + rev_s
    n = len(new_s)
    
    # KMP table to store the longest prefix which is also suffix
    lps = [0] * n
    j = 0
    
    # Build the lps array
    for i in range(1, n):
        while (j > 0 and new_s[i] != new_s[j]):
            j = lps[j - 1]
        if new_s[i] == new_s[j]:
            j += 1
            lps[i] = j
    
    # The length of the longest palindromic suffix
    longest_palindromic_suffix_length = lps[-1]
    
    # Characters to add in front
    to_add = rev_s[:len(s) - longest_palindromic_suffix_length]
    
    return to_add + s
← Back to All Questions