Shortest Palindrome
HardPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
Check each prefix of the string to find the longest palindrome starting from index 0, then add the remaining characters in reverse order to the front.
Algorithm
- Iterate through each prefix of the string from index 0 to n-1
- For each prefix, check if it forms a palindrome
- Keep track of the longest palindrome prefix
- Take the remaining characters after the longest palindrome prefix
- Reverse these characters and add them to the front of the original string
Walkthrough
In this approach, we iterate through each prefix of the string and check if it forms a palindrome starting from index 0. Once we find the longest palindrome prefix, we take the remaining characters, reverse them, and add them to the front of the original string.
public String shortestPalindrome(String s) { int n = s.length(); int maxLen = 0; // Check each prefix for (int i = 0; i < n; i++) { if (isPalindrome(s, 0, i)) { maxLen = i + 1; } } // Get the remaining characters and reverse them String remaining = s.substring(maxLen); StringBuilder reversed = new StringBuilder(remaining).reverse(); return reversed.toString() + s;} private boolean isPalindrome(String s, int start, int end) { while (start < end) { if (s.charAt(start) != s.charAt(end)) { return false; } start++; end--; } return true;}Complexity
Time
O(n²) where n is the length of the string - we need to check each prefix and for each prefix we check if it's a palindrome
Space
O(n) for storing the reversed substring
Trade-offs
Pros
Simple to understand and implement
Works well for small strings
Cons
Very inefficient for large strings
Performs redundant checks for palindrome verification
Use KMP (Knuth-Morris-Pratt) algorithm to find the longest palindrome prefix by concatenating the original string with its reverse and a delimiter.
Algorithm
- Create a new string temp = s + "#" + reverse(s)
- Compute the LPS (Longest Proper Prefix which is also Suffix) array using KMP algorithm
- The last value in LPS array gives the length of the longest palindrome prefix
- Take the remaining characters after the longest palindrome prefix
- Reverse these characters and add them to the front of the original string
Walkthrough
This approach uses the KMP algorithm to efficiently find the longest palindrome prefix. We create a new string by concatenating the original string, a special character (that doesn't appear in the string), and the reverse of the original string. Then we use KMP to find the longest proper prefix that is also a suffix.
public String shortestPalindrome(String s) { String temp = s + "#" + new StringBuilder(s).reverse().toString(); int[] lps = computeLPSArray(temp); // Length of the longest palindrome prefix int longest = lps[lps.length - 1]; // Get the remaining characters, reverse them and add to front String remaining = s.substring(longest); return new StringBuilder(remaining).reverse().toString() + s;} private int[] computeLPSArray(String pattern) { int[] lps = new int[pattern.length()]; int len = 0; int i = 1; while (i < pattern.length()) { if (pattern.charAt(i) == pattern.charAt(len)) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } return lps;}Complexity
Time
O(n) where n is the length of the string - KMP algorithm runs in linear time
Space
O(n) for storing the concatenated string and LPS array
Trade-offs
Pros
More efficient than brute force approach
Uses pattern matching to avoid redundant comparisons
Linear time complexity
Cons
Requires understanding of KMP algorithm
Uses additional space for the concatenated string
Solutions
Solution
// https://leetcode.com/problems/shortest-palindrome/ using System.Text ; public partial class Solution { public string ShortestPalindrome ( string s ) { for ( var i = s . Length - 1 ; i >= 0 ; -- i ) { var k = i ; var j = 0 ; while ( j < k ) { if ( s [ j ] == s [ k ]) { ++ j ; -- k ; } else { break ; } } if ( j >= k ) { var sb = new StringBuilder ( s . Length * 2 - i - 1 ); for ( var l = s . Length - 1 ; l >= i + 1 ; -- l ) { sb . Append ( s [ l ]); } sb . Append ( s ); return sb . ToString (); } } return string . Empty ; } }public class Shortest_Palindrome { public class Solution { public String shortestPalindrome ( String s ) { if ( s == null || s . length () == 0 ) { return "" ; } int i = 0 , n = s . length (); for ( int j = n - 1 ; j >= 0 ; -- j ) { // @note: j will cross i, eg. making i=2 for "adcba" if ( s . charAt ( i ) == s . charAt ( j )) { ++ i ; } } // now [0, i) is a possible palindrome, but need extra check if ( i == n ) { return s ; } String remaining = s . substring ( i ); // need to add reverse part of it String rem_rev = new StringBuilder ( remaining ). reverse (). toString (); return rem_rev + shortestPalindrome ( s . substring ( 0 , i )) + remaining ; } } } ############ class Solution { public String shortestPalindrome ( String s ) { int base = 131 ; int mul = 1 ; int mod = ( int ) 1 e9 + 7 ; int prefix = 0 , suffix = 0 ; int idx = 0 ; int n = s . length (); for ( int i = 0 ; i < n ; ++ i ) { int t = s . charAt ( i ) - 'a' + 1 ; prefix = ( int ) ((( long ) prefix * base + t ) % mod ); suffix = ( int ) (( suffix + ( long ) t * mul ) % mod ); mul = ( int ) ((( long ) mul * base ) % mod ); if ( prefix == suffix ) { idx = i + 1 ; } } if ( idx == n ) { return s ; } return new StringBuilder ( s . substring ( idx )). reverse (). toString () + s ; } }''' reversed(): returns a reverse iterator >>> s = "aabbcc" >>> reversed(s) <reversed object at 0x108384a60> >>> ''.join(reversed(s)) 'ccbbaa' >>> s = "aabbcc" >>> s[::-1] 'ccbbaa' ''' class Solution : def shortestPalindrome ( self , s : str ) -> str : if not s : return "" i , n = 0 , len ( s ) for j in range ( n - 1 , - 1 , - 1 ): if s [ i ] == s [ j ]: i += 1 if i == n : return s remaining = s [ i :] rem_rev = remaining [:: - 1 ] return rem_rev + self . shortestPalindrome ( s [: i ]) + remaining ############ class Solution : def shortestPalindrome ( self , s : str ) -> str : base = 131 mod = 10 ** 9 + 7 n = len ( s ) prefix = suffix = 0 mul = 1 idx = 0 for i , c in enumerate ( s ): prefix = ( prefix * base + ( ord ( c ) - ord ( 'a' ) + 1 )) % mod suffix = ( suffix + ( ord ( c ) - ord ( 'a' ) + 1 ) * mul ) % mod mul = ( mul * base ) % mod if prefix == suffix : idx = i + 1 return s if idx == n else s [ idx :][:: - 1 ] + s ############ class Solution ( object ): # brutal force TLE def _shortestPalindrome ( self , s ): """ :type s: str :rtype: str """ def isPal ( cand ): start , end = 0 , len ( cand ) - 1 while start < end : if cand [ start ] != cand [ end ]: return False start += 1 end -= 1 return True n = len ( s ) ans = s [:: - 1 ] + s ansLen = 2 * len ( s ) for i in reversed ( range ( 0 , len ( s ) + 1 )): newPal = s [ i :][:: - 1 ] + s if isPal ( newPal ) and n + len ( s ) - i < ansLen : ansLen = n + len ( s ) - i ans = newPal return ans def shortestPalindrome ( self , s ): r = s [:: - 1 ] for i in range ( len ( s ) + 1 ): if s . startswith ( r [ i :]): return r [: i ] + s// OJ: https://leetcode.com/problems/shortest-palindrome/ // Time: O(N) // Space: O(1) ignoring the space taken by the answer class Solution { public: string shortestPalindrome ( string s ) { unsigned d = 16777619 , h = 0 , rh = 0 , p = 1 , maxLen = 0 ; for ( int i = 0 ; i < s . size (); ++ i ) { h = h * d + s [ i ] - 'a' ; rh += ( s [ i ] - 'a' ) * p ; p *= d ; if ( h == rh ) maxLen = i + 1 ; } return string ( rbegin ( s ), rbegin ( s ) + s . size () - maxLen ) + s ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.