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.

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

Input: s = "dedcba"
Output: "abcdedcba"

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.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Solution {
    public String shortestPalindrome(String s) {
        int n = s.length();

        // Brute-force approach to find the longest palindromic prefix
        int longestPalindromePrefixEnd = 0;
        for (int i = n; i >= 1; i--) {
            if (isPalindrome(s.substring(0, i))) {
                longestPalindromePrefixEnd = i;
                break;
            }
        }

        // Construct the shortest palindrome
        String suffix = s.substring(longestPalindromePrefixEnd);
        String prefix = new StringBuilder(suffix).reverse().toString();
        return prefix + s;
    }

    // Helper method to check if a given string is a palindrome
    public boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)

        # Brute-force approach to find the longest palindromic prefix
        longest_palindrome_prefix_end = 0
        for i in range(n, 0, -1):
            if self.is_palindrome(s[:i]):
                longest_palindrome_prefix_end = i
                break

        # Construct the shortest palindrome
        suffix = s[longest_palindrome_prefix_end:]
        prefix = suffix[::-1]
        return prefix + s

    # Helper method to check if a given string is a palindrome
    def is_palindrome(self, str: str) -> bool:
        left, right = 0, len(str) - 1
        while left < right:
            if str[left] != str[right]:
                return False
            left += 1
            right -= 1
        return True

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

Dry Run

Dry running the above code:

1
2
3
4
5
6
7
8
9

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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();
}