class Solution {
public:
std::string longestPalindrome(std::string s) {
if (s.size() < 2)
return s;
int len = s.size(), max_left = 0, max_len = 1, left, right;
for (int start = 0; start < len && len  start > max_len / 2;) {
left = right = start;
while (right < len  1 && s[right + 1] == s[right])
++right;
start = right + 1;
while (right < len  1 && left > 0 && s[right + 1] == s[left  1]) {
++right;
left;
}
if (max_len < right  left + 1) {
max_left = left;
max_len = right  left + 1;
}
}
return s.substr(max_left, max_len);
}
};
Accepted 4ms c++ solution.


In fact, I do not understand why your solution can be faster so much than the dp array method ..... As your method indeed is also to check all the possible palindrome char ....
The only reason you are so fast I think is because that the test cases contain many many duplicate chars !!!
You have skipped the duplicate chars to make the beginning searching points very large!!!!


@RainbowSecret I think you are right.My algorithm is dp also run O(N*2), but time 147ms.

Hi, thanks for sharing your solution. My solution is similar to yours, but it achieved 6ms, slower than yours.
Then I found your code do early termination with (len  start > max_len / 2), it is really effective. I modified my code and it achieve 3 ms. Thanks your solution again!string longestPalindrome(string s) { if(s.empty()) return s; int max_beg=0, max_end=0; int beg=0, end=0; for(int i=0; i<s.size() && (s.size()1i) > (max_end  max_beg)/2; ++i){ beg = end = i; while(end+1 < s.size() && s[beg] == s[end+1]){ end++; i++; } while(beg1>=0 && end+1<s.size()){ if(s[beg1] != s[end+1]) break; beg; end++; } if( endbeg > max_endmax_beg){ max_beg=beg; max_end=end; } } return s.substr(max_beg, max_endmax_beg+1); }

@RainbowSecret
Agree.
My implementation used two pointers to scan repeated chars, and got AC in 6ms.I tried this code, 6ms, same with mine.
Then I removed the optimization for repeated chars, it went up to 49ms.


@prime_tang said in Accepted 4ms c++ solution.:
start < len && len  start > max_len / 2
start < len is redundant since len  start > max_len / 2 has said that.

@prime_tang Thanks for sharing. I implement it use c 3ms.
char* longestPalindrome(char* s) { int result_index = 1; int result_len = 0; int s_len = strlen(s); for (int i = 0; (s_len  i  1) * 2 + 1 > result_len;) { int left = i  1, right = i + 1; while (right < s_len && s[right] == s[right1]) ++right; i = right; while (left >= 0 && right < s_len && s[left] == s[right]) { left; ++right; } if (right  left  1 > result_len) { result_len = right  left  1; result_index = left + 1; } } if (result_len == 0) return ""; char* result = (char*)malloc(sizeof(char)*(result_len+1)); strncpy(result, s + result_index, result_len); result[result_len] = '\0'; return result; }