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[])
	{
		System.out.println(shortestPal("abab"));
	}
	

}
		

Order of the Algorithm

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


Contribution

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

    Virendra Karappa

    Ninja Programmer