# Shortest Palindrome

This page explains Java solution to problem `Shortest Palindrome` using `KMP` algorithm.

## Problem Statement

Given a string `s`, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class ShortestPalindrome {
public String shortestPalindrome(String s) {
String sNew = s + "#" + reverse(s);

int[] kmp = new int[sNew.length()];
int n = sNew.length();
int start = 0, end = 1;
while(end < n) {
if(sNew.charAt(start) == sNew.charAt(end)) {
kmp[end] = start + 1;
start++;
end++;
}
else {
if(start == 0) kmp[end++] = 0;
else start = kmp[start - 1];
}
}
return reverse(s.substring(kmp[n - 1])) + s;
}

private String reverse(String s) {
int start = 0, end = s.length() - 1;
char[] cArr = s.toCharArray();
while(start < end) {
char ch = s.charAt(start);
cArr[start] = cArr[end];
cArr[end] = ch;
start++;
end--;
}
return new String(cArr);
}
}
``````

## Time Complexity

O(N) Where
N is total number of elements in an input String

## Space Complexity

O(N) Where
N is total number of elements in an input String