Shortest Palindrome

Given a string s, form a shortest palindrome by appending characters at the start of the string.
Example: abab => babab. abcd => dcbabcd. ananab    => bananab.

Please try solving this problem before jumping on the solution

Click to learn

Subscribe for more updates

Preparing for interviews? IDeserve team is here to help.

Hone your coding skills!

AngryNerds Practice platform »

Algorithm Visualization

Code Snippet

package com.ideserve.virendra.questions;

public class ShortestPalindrome {
	public  static String shortestPal(String s)
		String rev_s = new StringBuilder(s).reverse().toString();
		//use special character to avoid overlap
		String l = s + "#" + rev_s; 
		int[] p = new int[l.length()];
		//build KMP table.
		//i -> suffix boundary
		//j -> prefix boundary
		for(int i=1; i<l.length(); i++)
			//update prefix boundary to previous match position
			int j = p[i-1];
			//move to the last prefix boundary match
			while(j>0 && l.charAt(i)!=l.charAt(j))
				j = p[j-1];
			//if prefix boundary matches suffix boundary,
			//increase prefix length 
			if(l.charAt(i) == l.charAt(j)) p[i] = j + 1;
		return rev_s.substring(0, s.length() - p[l.length() - 1]) + s;
	public static void main(String args[])


Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(n)


  • Sincere thanks from IDeserve community to Virendra Karappa for compiling current post.

    Virendra Karappa

    Ninja Programmer