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

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