public class Solution {
public String longestPalindrome(String s) {
if(s.length() < 2) return s;
int maxStart = 0;
int maxEnd = 0;
for(int i = 1; i < s.length(); i++){
if(i < s.length() 1 && s.charAt(i1) == s.charAt(i+1)){
int start = i2;
int end = i+2;
while(end < s.length() && start >= 0){
if(s.charAt(start) == s.charAt(end)){
start;
end++;
}
else break;
}
start++;
end;
if(end  start > maxEnd  maxStart) {
maxStart = start;
maxEnd = end;
}
}
if(s.charAt(i) == s.charAt(i1)){
int start = i2;
int end = i+1;
while(end < s.length() && start >= 0){
if(s.charAt(start) == s.charAt(end)){
start;
end++;
}
else break;
}
start++;
end;
if(end  start > maxEnd  maxStart) {
maxStart = start;
maxEnd = end;
}
}
}
return s.substring(maxStart, maxEnd+1);
}
}
I think the time complexity of my solution is O(n^2). Why it exceeded time limit?


@Eternal But actually it can be easily solved in
O(n)
instead of O(n^2), so try harder on this.

@LHearen Which way are you thinking of? I don't know an easy O(n) one. And I think the three topvoted answers also are only O(n^2), not O(n).
@Eternal I just submitted it five times, every time it got accepted. With times 96 ms to 116 ms. And the slowest accepted solution shown in the distribution graph took 240 ms. Are you sure you got "Time Limit Exceeded"?



@StefanPochmann @Eternal Sorry, my mistake. But indeed, your solution is little bit complicated. Here is my cleaner solution O(n^2) as yours, in C++.
class Solution { public: string longestPalindrome(string s) { int sLen = s.length(), maxLen = 0, maxStart = 0; int i = 0, l = 0, r = 0, len = 0; while(i<=sLenmaxLen/2) { l = r = i; while(r<sLen1 && s[r+1]==s[r]) r++; i = r+1; while(l>0 && r<sLen1 && s[r+1]==s[l1]) l, r++; len = rl+1; if(maxLen < len) maxLen = len, maxStart = l; } return s.substr(maxStart, maxLen); } };