• ``````// 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);
}
};
``````

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