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
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 ; } }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.