# Java Solution AC O(N^2) with lots of comments.

• ``````public class Solution {
public String shortestPalindrome(String s) {
//a or empty string
if (s.length()<2) return s;

char[] c=s.toCharArray();
//We can always use the first character of an odd length solution
int r=s.length()%2;

//start at the end, the first one we find will be the longest internal palindrome
for(int j=c.length-1;j>=0;j--) {
if(c[0]==c[j]) {
int i=j;
int nk=j;
boolean fail=false;
//check that it's a palindrome till we hit the halfway mark
for(;i>=j/2;i--) {
if(c[i]==c[j]) {
//keep track of where to pick up if this fails
nk=j;
}
if (c[j-i]!=c[i]) {
//not a palindrome
fail=true;
break;
}
}
if (!fail) {
//we found the longest one, we're done
r=j;
break;
} else {
//pick up at a possible palindrome spot
j=nk;
}
}
}
//If the whole thing is a palindrome then return it unchanged
if (r==s.length()) return s;
StringBuffer prepend=new StringBuffer();
//otherwise reverse prepend to the string
for(int i=c.length-1;i>r;i--) {
prepend.append(c[i]);
}
//and put the rest of the word on the end.
prepend.append(s);

return prepend.toString();
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.