Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Shortest Palindrome

HARDProblemSolveExternal Links

Description

You are given a string s. Your task is to transform s into a palindrome by only adding characters to the front (beginning) of the string.

Return the shortest palindrome that can be formed through this operation.

A palindrome is a string that reads the same forwards and backwards. For example, "racecar" and "noon" are palindromes.

The key constraint is that you can only prepend characters — you cannot append, remove, or rearrange any existing characters in s.

Examples

Example 1

Input: s = "aacecaaa"

Output: "aaacecaaa"

Explanation: The longest prefix of s that is already a palindrome is "aacecaa" (indices 0 through 6). The remaining suffix is "a" (index 7). We reverse this suffix to get "a" and prepend it to the original string: "a" + "aacecaaa" = "aaacecaaa". This is the shortest palindrome achievable by front-insertion.

Example 2

Input: s = "abcd"

Output: "dcbabcd"

Explanation: No multi-character prefix of "abcd" forms a palindrome. Only the single character "a" is trivially a palindrome. The remaining suffix is "bcd". We reverse it to get "dcb" and prepend: "dcb" + "abcd" = "dcbabcd".

Example 3

Input: s = "aba"

Output: "aba"

Explanation: The entire string "aba" is already a palindrome, so no characters need to be added. The answer is the string itself.

Constraints

  • 0 ≤ s.length ≤ 5 × 10^4
  • s consists of lowercase English letters only.

Editorial

Brute Force

Intuition

Before diving into clever algorithms, let us think about what it means to create the shortest palindrome by adding characters to the front.

Imagine you have the string written on a strip of paper. You want to extend it from the left side until the whole strip reads the same in both directions. The fewer characters you add, the better.

The crucial observation is: we need to find the longest prefix of s that is already a palindrome. Once we know that, everything after that palindromic prefix is the "leftover" — and we simply reverse that leftover and stick it in front.

For example, with s = "aacecaaa", the longest palindromic prefix is "aacecaa" (7 characters). The leftover is "a" (1 character). Reverse it and prepend: result is "a" + "aacecaaa".

The brute force idea is straightforward: try every possible prefix length from longest to shortest. For each candidate, check if that prefix is a palindrome. The first (longest) one we find gives us the answer.

Step-by-Step Explanation

Let's trace through with s = "abcd":

Step 1: Start with the full string as the candidate prefix: "abcd" (length 4).

  • Is "abcd" a palindrome? Compare first char 'a' with last char 'd' → mismatch. Not a palindrome.

Step 2: Shrink candidate to "abc" (length 3).

  • Is "abc" a palindrome? Compare 'a' with 'c' → mismatch. Not a palindrome.

Step 3: Shrink candidate to "ab" (length 2).

  • Is "ab" a palindrome? Compare 'a' with 'b' → mismatch. Not a palindrome.

Step 4: Shrink candidate to "a" (length 1).

  • Is "a" a palindrome? A single character is always a palindrome. Yes!

Step 5: The longest palindromic prefix is "a" (length 1). The leftover suffix is s[1:] = "bcd".

Step 6: Reverse the leftover: "bcd" → "dcb". Prepend to original: "dcb" + "abcd" = "dcbabcd".

Result: "dcbabcd"

Brute Force — Checking Prefixes for Palindrome — Watch how we shrink the candidate prefix from the full string down until we find the longest prefix that is a palindrome.

Algorithm

  1. Start with the full string length n as the candidate prefix length.
  2. For each candidate length from n down to 1:
    • Extract the prefix s[0..len-1].
    • Check if this prefix is a palindrome (compare characters from both ends inward).
    • If it is a palindrome, stop — this is the longest palindromic prefix.
  3. Compute the leftover: suffix = s[len..n-1].
  4. Reverse the leftover suffix.
  5. Return reversed_suffix + s.

Code

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) return s;
        
        // Find the longest palindromic prefix
        int longestPalinPrefix = 0;
        for (int len = n; len >= 1; len--) {
            if (isPalindrome(s, 0, len - 1)) {
                longestPalinPrefix = len;
                break;
            }
        }
        
        // Get the suffix that is not part of the palindromic prefix
        string suffix = s.substr(longestPalinPrefix);
        string reversed_suffix = string(suffix.rbegin(), suffix.rend());
        return reversed_suffix + s;
    }
    
private:
    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        if n <= 1:
            return s
        
        def is_palindrome(left: int, right: int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
        
        # Find the longest palindromic prefix
        longest_palin_prefix = 0
        for length in range(n, 0, -1):
            if is_palindrome(0, length - 1):
                longest_palin_prefix = length
                break
        
        # Reverse the leftover suffix and prepend
        suffix = s[longest_palin_prefix:]
        return suffix[::-1] + s
class Solution {
    public String shortestPalindrome(String s) {
        int n = s.length();
        if (n <= 1) return s;
        
        // Find the longest palindromic prefix
        int longestPalinPrefix = 0;
        for (int len = n; len >= 1; len--) {
            if (isPalindrome(s, 0, len - 1)) {
                longestPalinPrefix = len;
                break;
            }
        }
        
        // Get the suffix not part of the palindromic prefix
        String suffix = s.substring(longestPalinPrefix);
        StringBuilder reversed = new StringBuilder(suffix).reverse();
        return reversed.toString() + s;
    }
    
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n²)

In the worst case (e.g., s = "abcd...z"), none of the longer prefixes are palindromes. We check prefixes of length n, n-1, n-2, …, 1. Each palindrome check takes O(n) time in the worst case. The total work is O(n) + O(n-1) + … + O(1) = O(n²).

Space Complexity: O(n)

We create the reversed suffix and the result string, both of which are at most O(n) in size. The palindrome check itself uses O(1) extra space.

Why This Approach Is Not Efficient

The brute force approach checks every possible prefix length and, for each, verifies if it is a palindrome from scratch. This results in O(n²) time.

With n up to 5 × 10⁴, this means up to 2.5 × 10⁹ character comparisons in the worst case — far too slow for typical time limits of 1-2 seconds.

The inefficiency comes from redundant palindrome checks. When we check if "abcba" is a palindrome and then check "abcb", we don't reuse any work from the previous check. Each verification starts from scratch.

What we need is a way to find the longest palindromic prefix in a single O(n) pass. The KMP algorithm's failure function provides exactly this insight: by concatenating the string with its reverse separated by a special character, the LPS (Longest Proper Prefix which is also Suffix) array's last value directly tells us the length of the longest palindromic prefix.

Optimal Approach - KMP (LPS Array)

Intuition

The key insight is a clever reformulation: the longest palindromic prefix of s is the same as the longest prefix of s that matches a suffix of reverse(s).

Why? If s[0..k] is a palindrome, then s[0..k] read backwards equals itself. But s[0..k] read backwards is also a suffix of reverse(s). So a palindromic prefix of s is also a prefix of s that appears as a suffix of reverse(s).

This is precisely what the KMP failure function (LPS array) computes! The LPS array for a string tells us, for each position, the length of the longest proper prefix that is also a suffix.

Here is the strategy:

  1. Build a combined string: combined = s + '#' + reverse(s). The '#' separator ensures the prefix from s never "bleeds" into the reversed portion.
  2. Compute the LPS (failure function) array for this combined string.
  3. The last value of the LPS array is the length of the longest palindromic prefix of s.
  4. Take everything after that prefix, reverse it, and prepend it.

For example, with s = "aacecaaa":

  • reverse(s) = "aaacecaa"
  • combined = "aacecaaa#aaacecaa"
  • The LPS array's last value is 7, meaning the longest palindromic prefix has length 7 ("aacecaa").
  • Leftover: s[7:] = "a", reversed: "a", result: "a" + "aacecaaa" = "aaacecaaa".
Diagram showing how s + '#' + reverse(s) is formed and how the LPS array reveals the longest palindromic prefix
Diagram showing how s + '#' + reverse(s) is formed and how the LPS array reveals the longest palindromic prefix

Step-by-Step Explanation

Let's trace through with s = "aacecaaa":

Step 1: Reverse the string: rev = "aaacecaa".

Step 2: Build the combined string: combined = "aacecaaa" + "#" + "aaacecaa" = "aacecaaa#aaacecaa". The combined string has length 17.

Step 3: Compute the LPS array for the combined string. We initialize lps[0] = 0 and process each character:

  • i=1, char='a': Compare with combined[0]='a' → match. lps[1]=1.
  • i=2, char='c': Compare with combined[1]='a' → mismatch. Fall back. lps[2]=0.
  • i=3, char='e': No prefix match. lps[3]=0.
  • i=4, char='c': No prefix match. lps[4]=0.
  • i=5, char='a': Compare with combined[0]='a' → match. lps[5]=1.
  • i=6, char='a': Compare with combined[1]='a' → match. lps[6]=2.
  • i=7, char='a': Compare with combined[2]='c' → mismatch. Fall back to lps[1]=1. Compare combined[1]='a' → match. lps[7]=2.
  • i=8, char='#': No match possible. lps[8]=0.
  • i=9, char='a': Match with combined[0]. lps[9]=1.
  • i=10, char='a': Match with combined[1]. lps[10]=2.
  • i=11, char='a': Mismatch with combined[2]='c'. Fall back. lps[11]=2.
  • i=12, char='c': Match with combined[2]='c'. lps[12]=3.
  • i=13, char='e': Match with combined[3]='e'. lps[13]=4.
  • i=14, char='c': Match with combined[4]='c'. lps[14]=5.
  • i=15, char='a': Match with combined[5]='a'. lps[15]=6.
  • i=16, char='a': Match with combined[6]='a'. lps[16]=7.

Step 4: The last LPS value is lps[16] = 7. This means the longest palindromic prefix of s has length 7.

Step 5: The leftover suffix is s[7:] = "a". Reverse it: "a".

Step 6: Prepend: "a" + "aacecaaa" = "aaacecaaa".

Result: "aaacecaaa"

KMP LPS Array Construction on Combined String — Watch how the LPS (failure function) array is built for the combined string s + '#' + reverse(s). The last LPS value reveals the longest palindromic prefix length.

Algorithm

  1. Reverse the input string s to get rev.
  2. Construct combined = s + '#' + rev.
  3. Compute the LPS (Longest Proper Prefix which is also Suffix) array for combined:
    • Initialize lps[0] = 0, set len = 0, i = 1.
    • While i < combined.length:
      • If combined[i] == combined[len]: set lps[i] = len + 1, increment both i and len.
      • Else if len > 0: set len = lps[len - 1] (fall back).
      • Else: set lps[i] = 0, increment i.
  4. The longest palindromic prefix length is lps[last index].
  5. Extract the leftover suffix: s[lps_last:].
  6. Reverse the leftover and prepend to s.
  7. Return the result.

Code

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) return s;
        
        string rev = string(s.rbegin(), s.rend());
        string combined = s + "#" + rev;
        int m = combined.size();
        
        // Compute LPS array
        vector<int> lps(m, 0);
        int len = 0;
        int i = 1;
        while (i < m) {
            if (combined[i] == combined[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        int palindromeLen = lps[m - 1];
        string suffix = s.substr(palindromeLen);
        string reversed_suffix(suffix.rbegin(), suffix.rend());
        return reversed_suffix + s;
    }
};
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s
        
        rev = s[::-1]
        combined = s + "#" + rev
        m = len(combined)
        
        # Compute LPS array
        lps = [0] * m
        length = 0
        i = 1
        while i < m:
            if combined[i] == combined[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        
        palindrome_len = lps[-1]
        suffix = s[palindrome_len:]
        return suffix[::-1] + s
class Solution {
    public String shortestPalindrome(String s) {
        int n = s.length();
        if (n <= 1) return s;
        
        String rev = new StringBuilder(s).reverse().toString();
        String combined = s + "#" + rev;
        int m = combined.length();
        
        // Compute LPS array
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        while (i < m) {
            if (combined.charAt(i) == combined.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        int palindromeLen = lps[m - 1];
        String suffix = s.substring(palindromeLen);
        String reversedSuffix = new StringBuilder(suffix).reverse().toString();
        return reversedSuffix + s;
    }
}

Complexity Analysis

Time Complexity: O(n)

Building the reversed string takes O(n). Constructing the combined string takes O(n). Computing the LPS array runs in O(2n + 1) = O(n) — the KMP failure function processes each character at most twice (once when advancing i, once when falling back via len). The final string construction (slicing, reversing, concatenating) is also O(n). Total: O(n).

Space Complexity: O(n)

The combined string has length 2n + 1, so it uses O(n) space. The LPS array also uses O(n) space. The reversed string and result string each use O(n). Total auxiliary space: O(n).