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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Palindrome

Number: 214

Difficulty: Hard

Paid? No

Companies: Accenture, Google, Bloomberg, Microsoft, Amazon, TikTok, Uber, eBay, Pocket Gems

Problem Description

Given a string s, transform s into a palindrome by adding characters in front of it. The goal is to find and return the shortest palindrome that can be created using this transformation.

Key Insights

  • The main idea is to identify the longest prefix of s that is already a palindrome.
  • Once this prefix is identified, the remaining suffix can be reversed and prepended to s to form a complete palindrome.
  • A robust way to find the longest palindromic prefix is to use the KMP (Knuth-Morris-Pratt) algorithm on a constructed string made by concatenating s, a separator (such as '#'), and the reverse of s.
  • The prefix table computed from KMP helps determine the maximum matching prefix which is also a palindrome.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s, because building and processing the combined string takes linear time. Space Complexity: O(n), needed for the combined string and the prefix (LPS) table.

Solution

The solution builds a new string combined = s + '#' + reverse(s). The KMP prefix function is then computed for this string. The last value of the prefix table indicates the length of the longest prefix of s which is also a palindrome. The characters not included in this palindrome (the suffix) are then reversed and prepended to s to form the shortest palindrome. This approach leverages string matching techniques to efficiently determine the required palindrome structure.

Code Solutions

# Python solution using KMP prefix function
def shortestPalindrome(s: str) -> str:
    if not s:
        return s
    # Generate combined string with a separator
    rev_s = s[::-1]
    combined = s + "#" + rev_s
    n = len(combined)
    
    # Build KMP table (lps) for combined string
    lps = [0] * n
    for i in range(1, n):
        j = lps[i - 1]
        while j > 0 and combined[i] != combined[j]:
            j = lps[j - 1]
        if combined[i] == combined[j]:
            j += 1
        lps[i] = j
    
    # lps[-1] gives length of longest prefix of s which is palindrome
    longest_pal_pref = lps[-1]
    add_on = rev_s[:len(s) - longest_pal_pref]
    return add_on + s

# Example usage:
print(shortestPalindrome("aacecaaa"))  # Output: "aaacecaaa"
print(shortestPalindrome("abcd"))      # Output: "dcbabcd"
← Back to All Questions