Using idea similar to expanding from centers like in Longest palindromic substring.

For a string such as "aacecaaa", start expanding with centers from mid to 0 (no need to include mid, mid+1 as center for odd length string).

The first center that reaches -1 on the left on expanding will give the shortest palindrome.

In above case, it will be center "e" "e". Take the substring from the index at which expansion ended on the right, reverse it and pre-pend to original string to obtain shortest palindrome.

In above case, "a" + "aacecaaa".

```
public String shortestPalindrome(String s) {
int mid = s.length()/2;
int[] res = expand(s, mid, mid);
if (res[0] == -1)
{
if ((s.length() % 2) == 0)
{
return (new StringBuilder(s.substring(res[1]))).reverse().toString() + s;
}
else
{
return s;
}
}
// for even length string, check n/2 n/2+1 also as center for expansion
if ((s.length() % 2) == 0)
{
if (expand(s, mid, mid+1)[0] == -1)
{
return s;
}
}
for (int i=mid-1; i>=0; i--)
{
int[] res1 = expand(s, i, i+1);
if (res1[0] == -1)
{
return (new StringBuilder(s.substring(res1[1]))).reverse().toString() + s;
}
int[] res2 = expand(s, i, i);
if (res2[0] == -1)
{
return (new StringBuilder(s.substring(res2[1]))).reverse().toString() + s;
}
}
return "";
}
public int[] expand(String s, int left, int right)
{
while(left>=0 && right<s.length() && (s.charAt(left) == s.charAt(right)))
{
left--;
right++;
}
int result[] = {left, right};
return result;
}
```