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;
}
```