Watch 10 video solutions for Shortest Palindrome, a hard level problem involving String, Rolling Hash, String Matching. This walkthrough by Ashish Pratap Singh has 1,002,123 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: s = "aacecaaa" Output: "aaacecaaa"
Example 2:
Input: s = "abcd" Output: "dcbabcd"
Constraints:
0 <= s.length <= 5 * 104s consists of lowercase English letters only.Problem Overview: Given a string s, add characters only to the front so the entire string becomes a palindrome. The goal is to produce the shortest possible palindrome after the insertion.
Approach 1: Brute Force Prefix Check (O(n^2) time, O(1) space)
This method searches for the longest prefix of s that is already a palindrome. Iterate from the full length down to 0 and check whether s[0..i] forms a palindrome using two pointers from both ends. Once you find the longest palindromic prefix, reverse the remaining suffix and prepend it to the original string. The palindrome check runs in O(n) and is repeated up to n times, giving O(n^2) time overall with constant extra space.
This approach is straightforward and useful for understanding the structure of the problem. However, repeated palindrome checks make it inefficient for large inputs.
Approach 2: KMP-Based Prefix Matching (O(n) time, O(n) space)
The optimized solution converts the problem into a prefix-suffix matching task using the Knuth-Morris-Pratt algorithm from string matching. The key observation: you need the longest prefix of s that is also a palindrome. Construct a new string t = s + '#' + reverse(s). Then compute the KMP prefix function (LPS array) for t.
The final value in the LPS array tells you the length of the longest prefix of s that matches a suffix of reverse(s). This effectively identifies the longest palindromic prefix. Take the remaining suffix of s, reverse it, and prepend it to form the shortest palindrome. Building the LPS array takes linear time, so the entire algorithm runs in O(n) time and uses O(n) extra space.
This approach relies on prefix overlap detection, a core idea in string algorithms. Some implementations also use rolling hash or other hash function techniques to detect palindromic prefixes, but KMP guarantees deterministic O(n) performance.
Recommended for interviews: The KMP-based approach is the expected optimal solution because it reduces repeated palindrome checks to a single linear preprocessing step. Brute force demonstrates understanding of the palindrome prefix property, but interviewers typically look for the KMP insight or an equivalent linear-time string matching technique.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix Palindrome Check | O(n^2) | O(1) | Good for understanding the problem or when input sizes are small |
| KMP-Based Prefix Matching | O(n) | O(n) | Best general solution; avoids repeated palindrome checks |