Course4all

Shortest Palindrome

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Two Pointers.

Shortest Palindrome

You are given a string s. You can convert s to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
Hard

Examples

Input: s = "aacecaaa"
Output: "aaacecaaa"
Add 'a' to the front to get 'aaacecaaa', which is a palindrome.
Input: s = "abcd"
Output: "dcbabcd"
Add 'dcb' to the front to get 'dcbabcd'.
Approach 1

Level I: Brute Force (Prefix Check)

Intuition

The problem asks for the shortest palindrome created by adding chars to the front. This means we are effectively looking for the longest prefix of s that is already a palindrome.
Iterate through the string from the end. For each index i, check if s[0...i] is a palindrome. If it is, then the substring s[i+1...n-1] must be reversed and prepended to s.
⏱ O(N^2)💾 O(N)

Detailed Dry Run

s = "abcd" → prefix "abcd" is NOT → prefix "abc" is NOT → prefix "ab" is NOT → prefix "a" IS. Reverse "bcd" → "dcb". Result: "dcbabcd".
java
public String shortestPalindrome(String s) {
    int n = s.length();
    String rev = new StringBuilder(s).reverse().toString();
    for (int i = 0; i < n; i++) {
        if (s.substring(0, n - i).equals(rev.substring(i))) {
            return rev.substring(0, i) + s;
        }
    }
    return "";
}

⚠️ Common Pitfalls & Tips

Inefficient for large N (O(N^2) due to substring/startswith checks inside a loop).
Approach 2

Level II: Better (Two Pointers Recursion)

Intuition

We can use two pointers to find the largest prefix that could be a palindrome. We match characters from the beginning and end. If they match, we move both. If not, we skip the end character. Finally, we recurse on the unmatched middle part.
⏱ O(N^2) worst case, but faster on average💾 O(N)

Detailed Dry Run

s="aacecaaa". i=0, j=7. s[0]==s[7]... Match up to some point. Recurse.
java
public String shortestPalindrome(String s) {
    int j = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == s.charAt(j)) j++;
    }
    if (j == s.length()) return s;
    String suffix = s.substring(j);
    return new StringBuilder(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;
}

⚠️ Common Pitfalls & Tips

O(N^2) in worst case (e.g., "aaaaa...ab"). Recursion depth can be an issue.
Approach 3

Level III: Optimal (KMP Longest Prefix Function)

Intuition

We can use the KMP pattern matching logic (next array or lps array) to find the longest prefix that is a palindrome in O(N) time. We construct a temporary string T = s + "#" + reverse(s).
In the string s + "#" + rev(s), the last value of the KMP lookup table gives the length of the longest prefix of s that matches a suffix of rev(s), which is exactly the longest palindromic prefix.
⏱ O(N)💾 O(N)

Detailed Dry Run

s="aacecaaa", rev="aaacecaa". T="aacecaaa#aaacecaa". LPS[last] = 7. Prefix length 7 ("aacecaa") is palindrome. Prep rev[0...8-7] = "a". Result: "aaacecaaa".
java
public String shortestPalindrome(String s) {
    String temp = s + "#" + new StringBuilder(s).reverse().toString();
    int[] table = getTable(temp);
    return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
}
private int[] getTable(String s) {
    int[] table = new int[s.length()];
    int j = 0;
    for (int i = 1; i < s.length(); i++) {
        while (j > 0 && s.charAt(i) != s.charAt(j)) j = table[j - 1];
        if (s.charAt(i) == s.charAt(j)) j++;
        table[i] = j;
    }
    return table;
}

⚠️ Common Pitfalls & Tips

The separator '#' is necessary to ensure the prefix search doesn't cross the boundary into the reversed portion.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMedian of Two Sorted Arrays
Next Question →Minimum Window Subsequence