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: You are given a string s. The task is to add characters only to the front of the string so the final string becomes a palindrome. Among all possibilities, you must return the shortest possible palindrome.
The key observation: instead of trying to build a palindrome directly, find the longest prefix of the string that is already a palindrome. Once you know that prefix, reverse the remaining suffix and prepend it to the front.
Approach 1: Brute Force Prefix Check (O(n²) time, O(n) space)
Start from the full string and progressively shrink the right boundary while checking whether the prefix s[0..i] is a palindrome. For each candidate prefix, compare characters using two pointers from both ends. The first prefix that forms a palindrome is the longest palindromic prefix. After finding it, reverse the remaining suffix and prepend it to the original string. This approach is straightforward but inefficient because the palindrome check runs in O(n) and may execute up to n times, resulting in O(n²) time.
This method works well for understanding the problem structure and for small inputs. It mainly relies on basic string manipulation and two‑pointer comparisons.
Approach 2: KMP-Based Prefix Matching (O(n) time, O(n) space)
The optimal solution converts the problem into a prefix-suffix matching task using the KMP preprocessing technique from string matching. Construct a new string t = s + '#' + reverse(s). Then compute the KMP prefix function (LPS array) for t. The last value in the LPS array gives the length of the longest prefix of s that matches a suffix of reverse(s). That value directly represents the longest palindromic prefix of the original string.
Once this length is known, take the remaining suffix of s, reverse it, and prepend it. Because the prefix function processes the string in a single linear pass, the entire algorithm runs in O(n) time with O(n) additional space. This technique relies on prefix hashing ideas and pattern reuse concepts commonly used in hash functions and efficient string algorithms.
Recommended for interviews: Interviewers usually expect the KMP-based approach. The brute force solution shows you recognize the longest palindromic prefix idea, but the optimized method demonstrates deeper knowledge of linear-time string matching algorithms. If you quickly outline the brute force and then transition to the KMP optimization, it clearly shows strong algorithmic reasoning.
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.
C++
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.
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.
JavaScript
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 | Complexity |
|---|---|
| Brute Force Method | Time Complexity: O(n^2), where |
| Optimized KMP-based Method | Time Complexity: O(n), where |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix Palindrome Check | O(n²) | O(n) | Useful for understanding the problem or when input size is small and implementation simplicity matters |
| KMP-Based Prefix Matching | O(n) | O(n) | Best general solution for large strings and typical interview expectations |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,123 views views
Watch 9 more video solutions →Practice Shortest Palindrome with our built-in code editor and test cases.
Practice on FleetCode