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.

OR

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Solution

Method 1 - Brute Force

A brute force way to solve this problem is to keep adding characters from last one by one at front and keep checking whether current string is palindrome or not, at max we need to check characters equal to half of length of string because in worst case half of the string need to be added at front to make string palindrome.

Method 2 - Get the Suffix Which is Not Palindrome

Consider Java, answer for it will be avaJava.

We can start from the end, check if start and end don’t match, that is the problematic substring. If they match, it is good and can be part of suffix.

Code

Java
class Solution {
    public String shortestPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;

        while (j >= 0) {
            if (s.charAt(i) == s.charAt(j)) {
                i++;
            }
            j--;
        }

        if (i == s.length()) {
	        return s;
        }

        String suffix = s.substring(i);
        String prefix = new StringBuilder(suffix).reverse().toString();
        String mid = shortestPalindrome(s.substring(0, i));
        return prefix + mid + suffix;
    }
}
Python

Dry Run

Dry running the above code:

s = Java, i = 0, j = 3
s[i] != s[j] => j = 2
s[i] != s[j] => j = 1
s[i] != s[j] => j = 0
s[i] == s[j] => j = -1, i =1
So, only substring we can take as mid = s[0:i] = J
suffix = s[i:] = ava
prefix = ava as well.
Answer is avaJava.

Method 3 - Rabin Karp Algorithm

The problem asks us to find the shortest palindrome by prepending characters to the front of the string. We can use the Rabin-Karp algorithm to find the longest palindromic prefix efficiently.

Here are the steps:

  1. Initialize the variables for hash computation.
  2. Iterate through the string to calculate the hash values for the original string and compare them with the suffix’s hash values.
  3. Find the length of the longest palindromic prefix.
  4. Prepend the necessary characters from the reverse of the suffix and construct the shortest palindrome.

Code

Java
public class Solution {
    public String shortestPalindrome(String s) {
        int n = s.length();
        int palindromePrefixEnd = -1;
        long base = 29;
        long mod = 1000000007;
        long power = 1;
        long prefixHash = 0;
        long suffixHash = 0;

        for (int i = 0; i < n; i++, power = power * base % mod) {
            // Update prefix hash (left-to-right)
            prefixHash = (prefixHash * base + s.charAt(i) - 'a' + 1) % mod;

            // Update suffix hash (right-to-left by reverse hash logic)
            suffixHash = (suffixHash + (s.charAt(i) - 'a' + 1) * power) % mod;

            // Check if prefix and suffix hashes match
            if (prefixHash == suffixHash) {
                palindromePrefixEnd = i;
            }
        }

        // Get the characters to prepend and form the result
        String suffixToAdd =
            new StringBuilder(s.substring(palindromePrefixEnd + 1))
                .reverse()
                .toString();
        return suffixToAdd + s;
    }
}
Python
 class Solution:
     def shortestPalindrome(self, s: str) -> str:
         n = len(s)
         base = 29
         mod = 1000000007
         
         # Initialize hashes and power
         prefix_hash = 0
         suffix_hash = 0
         power = 1
         palindrome_prefix_end = -1
         
         for i in range(n):
             # Update prefix hash (left-to-right)
             prefix_hash = (prefix_hash * base + ord(s[i]) - ord('a') + 1) % mod
             
             # Update suffix hash (right-to-left)
             suffix_hash = (suffix_hash + (ord(s[i]) - ord('a') + 1) * power) % mod
             
             # Update power for next iteration
             power = power * base % mod
             
             # Check if current prefix is also a suffix (i.e., potential palindrome)
             if prefix_hash == suffix_hash:
                 palindrome_prefix_end = i
         
         # Form the shortest palindrome
         suffix_to_add = s[palindrome_prefix_end + 1:][::-1]
         return suffix_to_add + s

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 4 - Scan From Left and Right finding palindrome in center

We can solve this problem by using one of the methods which is used to solve the longest palindrome substring problem.

Specifically, we can start from the center and scan two sides. If read the left boundary, then the shortest palindrome is identified.

Code

Java
public String shortestPalindrome(String s) {
	if (s == null || s.length()<= 1)
		return s;

	String result = null;

	int len = s.length();
	int mid = len / 2;

	for (int i = mid; i >= 1; i--) {
		if (s.charAt(i) == s.charAt(i - 1)) {
			if ((result = scanFromCenter(s, i - 1, i)) != null)
				return result;
		} else {
			if ((result = scanFromCenter(s, i - 1, i - 1)) != null)
				return result;
		}
	}

	return result;
}

private String scanFromCenter(String s, int l, int r) {
	int i = 1;

	//scan from center to both sides
	for (; l - i >= 0; i++) {
		if (s.charAt(l - i) != s.charAt(r + i))
			break;
	}

	//if not end at the beginning of s, return null
	if (l - i >= 0)
		return null;

	StringBuilder sb = new StringBuilder(s.substring(r + i));
	sb.reverse();

	return sb.append(s).toString();
}