Code Implementation

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        rev = s[::-1]
        for i in range(len(s) + 1):
            if s.startswith(rev[i:]):
                return rev[:i] + s
      

class Solution {
public:
    string shortestPalindrome(string s) {
        string rev = s;
        reverse(rev.begin(), rev.end());
        for (int i = 0; i <= s.size(); ++i) {
            if (s.substr(0, s.size() - i) == rev.substr(i)) {
                return rev.substr(0, i) + s;
            }
        }
        return "";
    }
};
      

class Solution {
    public String shortestPalindrome(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        for (int i = 0; i <= s.length(); i++) {
            if (s.startsWith(rev.substring(i))) {
                return rev.substring(0, i) + s;
            }
        }
        return "";
    }
}
      

var shortestPalindrome = function(s) {
    let rev = s.split('').reverse().join('');
    for (let i = 0; i <= s.length; i++) {
        if (s.startsWith(rev.slice(i))) {
            return rev.slice(0, i) + s;
        }
    }
    return "";
};
      

Problem Description

Given a string s, you are asked to find and return the shortest palindrome you can form by adding characters in front of s. In other words, you may add as many characters as you want to the beginning of s so that the resulting string is a palindrome (reads the same forwards and backwards), but you cannot add characters elsewhere.

You must return one valid solution. The solution should be as short as possible. The input string s can be empty or contain only lowercase English letters.

Thought Process

The naive way to solve this problem is to try to make the string a palindrome by checking, for every possible prefix, if the string becomes a palindrome when that prefix is mirrored in front. This would mean, for each possible split, checking if the prefix is a palindrome and, if not, adding the minimal necessary characters.

However, this brute-force approach is inefficient, especially for longer strings. We want to optimize our solution by focusing on the longest palindromic prefix of s. If we can find the longest prefix of s that is itself a palindrome, then the minimal set of characters to add is simply the reverse of the remaining suffix, placed in front of s.

So, the challenge becomes: how do we efficiently find the longest palindromic prefix?

Solution Approach

• Step 1: Reverse the string s to get rev.
• Step 2: For each possible position i (from 0 up to the length of s), check if the original string s starts with the substring rev[i:]. In other words, see if the suffix of the reversed string matches the prefix of s.
• Step 3: The first position i where this is true indicates that the prefix s[0:len(s)-i] is a palindrome. The minimal characters to add are rev[0:i] (the unmatched part of the reversed string).
• Step 4: Return rev[0:i] + s as the shortest palindrome.

This method ensures that we are always adding the minimal number of characters in front, and leverages string matching to avoid unnecessary checks.

For even faster solutions, advanced algorithms like KMP (Knuth-Morris-Pratt) can be used to find the longest palindromic prefix in linear time, but the above method is simple and efficient enough for most practical cases.

Example Walkthrough

Let's take the input s = "aacecaaa".

• Reverse: rev = "aaacecaa"
• Check if s starts with rev[0:] = "aaacecaa" → No
• Check if s starts with rev[1:] = "aacecaa" → Yes
• Since s starts with rev[1:], the unmatched part is rev[0:1] = "a"
• Result: "a" + "aacecaaa" = "aaacecaaa"

The process stops at i = 1, and we prepend "a" to form the shortest palindrome.

Time and Space Complexity

• Brute-force Approach: For each possible prefix, check if it’s a palindrome (O(N) per check), for N prefixes. Total: O(N²).
• Optimized Approach (as above): For each position, compare the prefix and suffix. Each check can take up to O(N) time, so worst case is still O(N²), but with string methods and early exits, it is much faster in practice.
• Space Complexity: O(N) for storing the reversed string and possibly the result.

With advanced string matching algorithms (like KMP), the time complexity can be improved to O(N), but the presented solution is simple and suffices for most cases.

Summary

The key insight is to find the longest palindromic prefix of the input string. By reversing the string and checking for the largest overlap, we can efficiently determine the minimal set of characters to prepend. This approach avoids unnecessary brute-force checks and leverages string operations to yield a concise and elegant solution.