# Shortest Palindrome
**Difficulty:** HARD
[External](https://leetcode.com/problems/shortest-palindrome)
Canonical: https://scaleengineer.com/dsa/problems/shortest-palindrome
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Data structures:** String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Google](https://scaleengineer.com/companies/google), [Visa](https://scaleengineer.com/companies/visa), [eBay](https://scaleengineer.com/companies/ebay), [Pocket Gems](https://scaleengineer.com/companies/pocket-gems)
---
## Problem
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 * 104`
* `s` consists of lowercase English letters only.

# Approaches
## Brute Force Approach
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.
**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
**Pros:** Simple to understand and implement; Works well for small strings
**Cons:** Very inefficient for large strings; Performs redundant checks for palindrome verification
### Explanation
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.

```java
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;
}
```
### Algorithm
1. Iterate through each prefix of the string from index 0 to n-1
2. For each prefix, check if it forms a palindrome
3. Keep track of the longest palindrome prefix
4. Take the remaining characters after the longest palindrome prefix
5. Reverse these characters and add them to the front of the original string

## KMP Algorithm Approach
Use KMP (Knuth-Morris-Pratt) algorithm to find the longest palindrome prefix by concatenating the original string with its reverse and a delimiter.
**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
**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
### Explanation
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.

```java
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;
}
```
### Algorithm
1. Create a new string temp = s + "#" + reverse(s)
2. Compute the LPS (Longest Proper Prefix which is also Suffix) array using KMP algorithm
3. The last value in LPS array gives the length of the longest palindrome prefix
4. Take the remaining characters after the longest palindrome prefix
5. Reverse these characters and add them to the front of the original string

# Solutions
### CSharp

```csharp
// 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 ; } }
```

### Java

```java
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 ; } }
```

### Python

```python
''' 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
```

### CPP

```cpp
// 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 ; } };
```