Course4all
Join us on telegram
Home/dsa/Two Pointers/Shortest Palindrome

Shortest Palindrome

Master this topic with zero to advance depth.

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.

← Previous QuestionMedian of Two Sorted Arrays
Next Question →Minimum Window Subsequence