Shortest Palindrome - Solution & Explanation
Problem Statement
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 * 104sconsists of lowercase English letters only.
Approach Overview
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 1: Brute Force Method
The brute force approach involves checking each prefix of the string to determine if it forms a palindrome. We progressively add characters from the end of the string to the beginning until a valid palindrome is formed.
In this Python solution, we start by checking if the entire string s is already a palindrome. If it is, we return it immediately. Otherwise, we iteratively reduce the considered prefix of s and check if it forms a palindrome. Once a palindromic prefix is found, we append the reverse of the unmatched suffix before s.
Complexity
Time Complexity: O(n^2), where n is the length of the string, due to the repeated palindrome checks.
Space Complexity: O(n) for storing the reversed string.
Approach 2: Optimized KMP-based Method
This approach uses the KMP (Knuth-Morris-Pratt) algorithm's partial match table (LPS array) to efficiently find the largest palindromic prefix. We concatenate the string with its reverse and compute the LPS array for substring match optimization.
In this Java solution, the string is concatenated with a separator and its reverse to form temp. The LPS array is used to find the longest prefix which is also a palindrome. We then reverse the remaining suffix of the original string and prepend it to s to produce the shortest palindrome.
Code
Java
JavaScript
Complexity
Time Complexity: O(n), where n is the length of the string, due to linear time computation of the LPS array.
Space Complexity: O(n) for the LPS array and interim reversed string.
Approach 3: Default Approach
Try this approach in the editor →Approach 4: KMP Algorithm
According to the problem description, we need to reverse the string s to obtain the string rev, and then find the longest common part of the suffix of the string rev and the prefix of the string s. We can use the KMP algorithm to concatenate the string s and the string rev and find the longest common part of the longest prefix and the longest suffix.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Method | Time Complexity: O(n^2), where |
| Optimized KMP-based Method | Time Complexity: O(n), where |
| Default Approach | — |
| KMP Algorithm | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Rabin Karp - Shortest Palindrome - Leetcode 214 • NeetCodeIO • 33,913 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Shortest Palindrome easy or hard?
Shortest Palindrome Python/Java solution
How to solve Shortest Palindrome in O(n)?
What is the best approach for Shortest Palindrome?
Is Shortest Palindrome asked at Google/Amazon/Meta?
What data structure is used in Shortest Palindrome?
What is the time complexity of Shortest Palindrome?
Ready to solve this problem?
Practice Shortest Palindrome with our built-in code editor and test cases.
Practice on FleetCode