# Simple Java solution

• The main idea is to find the longest palindrome from the first index, cost O(n)

``````public String shortestPalindrome(String s) {
if(s.length() == 0) return "";
int len = s.length(), left, right,  maxLen = 0;
for(int i = 0 ; i < len;){
left = right = i;
while(right < len - 1 && s.charAt(right) == s.charAt(right + 1))
right ++;

i = right + 1;

while(left > 0 && right < len - 1 && s.charAt(left - 1) == s.charAt(right + 1)){
left --;
right ++;
}

if(left == 0 && maxLen < right + 1){
maxLen = right + 1;
}
}

String prefix = new StringBuilder(s.substring(maxLen)).reverse().toString();

return prefix + s;
}``````

• I think the complexity is not O(n)
In the for loop, in most cases, variable i would be increased by 1 at a time. However, the second while loop, might already take O(n) to extend the palindrome centered at left and right. So in the worst case, this algorithm would be O(n^2) or precisely O(1/2 * n^2).
Or am I wrong?

• This post is deleted!

• Seems like O(n^2) to me as well because take aacecaaa for example, when i is at index e, the runtime for e itself is already O(n), then you loop through all the character which makes it O(n^2).

• @QiZhang1
I think it is better than o(n^2), I tried to use the same idea by finding longest palindrome from index 0, but ending with ELT, but this solution only takes 8ms.. man, so fast...

• excellent, it's so fast. it's o(n/2), not o(n^2). try case like "aaa...aaa" or "abcd...zabcd...z".

• @QiZhang1 try case like "aaaa....aaa" and "abcd...zabcd...z", in fact, it's o(n/2), not o(n^2)

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