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.The goal of #214 Shortest Palindrome is to transform a string into the shortest possible palindrome by adding characters only to the front. A key observation is that we should find the longest prefix of the string that is already a palindrome. Once identified, the remaining suffix can be reversed and prepended to form the final result.
Efficient solutions rely on string matching techniques such as KMP-based prefix function or rolling hash. By comparing the original string with its reversed version, we can quickly detect the longest palindromic prefix without checking every substring. Rolling hash computes forward and backward hashes while scanning the string, while the KMP approach builds a pattern like s + '#' + reverse(s) to determine the longest match.
Both approaches reduce repeated palindrome checks and achieve near linear performance, making them suitable for large inputs commonly seen in coding interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Rolling Hash | O(n) | O(1) |
| KMP / Prefix Function (String Matching) | O(n) | O(n) |
Ashish Pratap Singh
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.
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.
1#include <string>
2
3std::string shortestPalindrome(std::string s) {
4 std::string rev_s = std::string(s.rbegin(), s.rend());
5 for (int i = s.size(); i >= 0; i--) {
6 if (s.substr(0, i) == rev_s.substr(s.size() - i)) {
7 return rev_s.substr(0, s.size() - i) + s;
8 }
9 }
10 return "";
11}
12This C++ solution uses a similar logic to Python, with minor syntax adjustments. It reverses the string using iterators and checks for palindromic prefixes. For each valid prefix, the solution constructs the shortest palindrome.
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.
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.
1function shortestPalindrome(s) {
2 constWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Shortest Palindrome problem appear in interviews at companies like Google, Amazon, and Meta. It tests knowledge of string algorithms, hashing, and pattern matching techniques.
The optimal approach finds the longest palindromic prefix of the string. This can be done efficiently using the KMP prefix function or rolling hash techniques. Both approaches avoid repeated substring checks and run in linear time.
Rolling hash allows you to compare the forward and reverse hashes of prefixes while scanning the string. When both hashes match, the prefix is a palindrome. This technique enables fast palindrome detection in O(n) time.
String matching algorithms such as the KMP prefix function and rolling hash are commonly used. They help identify the longest palindromic prefix efficiently without brute-force substring comparisons.
This JavaScript solution follows the same methodology as the Java solution using KMP. After forming new_s and computing the LPS array, it determines the longest palindromic prefix. The reversed suffix is prepended to form the shortest palindrome possible.