```
// There are basically two tricks here:
// 1. Check for palindrome by starting at middle and expanding to both sides (using half-indices to start "between" two chars).
// 2. Start the search at the middle of the string, as it has most potential of finding the longest palindrome, and quite early as soon as it's not possible to find a longer palindrome anymore.
// String: b a b a d
// Half-indices: 0 1 2 3 4 5 6 7 8
// Actual indices: 0 1 2 3 4
// String: c b b d
// Half-indices: 0 1 2 3 4 5 6
// Actual indices: 0 1 2 3
class Solution {
public:
string longestPalindrome(string s) {
string longest = "";
// Start at the middle, then circle.
const int middle = s.size()-1;
for (int delta = 0, direction = 1 ; ; delta += direction == -1 ? 1 : 0, direction *= -1) {
const int half_idx = middle + delta*direction;
// stop early if not possible to get longer anymore.
const int longest_possible = s.size() - delta;
if (longest.size() >= longest_possible) break;
string palin = expandPalindrome(s, half_idx);
if (palin.size() > longest.size()) {
longest = palin;
}
// Done.
if (half_idx == 0) break;
}
return longest;
}
static string expandPalindrome(const string& s, int half_idx) {
int left = half_idx/2;
int right = (half_idx+1)/2;
if (s[left] != s[right]) {
return "";
}
while (s[left] == s[right]) {
left--; right++;
// We are the largest palindrome we can become at this location.
if (-1 == left || right == s.size()) {
break;
}
}
return string(s, left+1, right-left-1);
}
};
```