⚡Flashcard Drill➔
NeetCode #172LC-214HardArrays & Hashing
← Back to All Problems

#172 · #214 · Shortest Palindrome(最短回文串)

📌 Problem Statement & Constraints

You are given a string s. You can convert it to a palindrome by adding characters in front of it. Return the shortest palindrome you can find this way. Constraints: 0 <= s.length <= 5 * 10^4.

💡 Core Algorithmic Approaches

  1. The characters we must prepend are exactly the reverse of the suffix of s that is not part of the longest palindromic prefix of s.
  2. So the task reduces to finding the longest prefix of s that is a palindrome.
  3. KMP trick: build the string t = s + "#" + reverse(s) and compute the KMP failure array. The last entry gives the length of the longest prefix of s that is also a suffix of reverse(s) -- which is exactly the longest palindromic prefix of s.
  4. Then the answer is reverse(s)[: len(s) - longest] + s.

💻 Benchmark Python3 Implementation

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        rev = s[::-1]
        # KMP failure array over s + '#' + reverse(s)
        t = s + "#" + rev
        lps = [0] * len(t)
        j = 0
        for i in range(1, len(t)):
            while j and t[i] != t[j]:
                j = lps[j - 1]             # fall back
            if t[i] == t[j]:
                j += 1
            lps[i] = j
        longest = lps[-1]                  # longest palindromic prefix of s
        return rev[:len(s) - longest] + s

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) with KMP: building the failure array is linear in the length of s + "#" + reverse(s).
💾 Space Complexity
O(n) for the failure array and the reversed string.

⚠️ Interview Pitfalls & Follow-ups

  • Using s + reverse(s) without the '#' separator: the failure array could match across the boundary, producing a prefix longer than len(s).
  • Searching for the longest palindromic prefix by brute force: O(n^2), far too slow at n = 5 * 10^4.
  • Reversing the wrong part: the prepended characters are reverse(s)[: n - longest], i.e. the reverse of the suffix that is not in the palindromic prefix.
  • Returning s when it is already a palindrome: longest == len(s) makes the prepended part empty, which the formula handles correctly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems