# Share accepted C++ code with O(n^2) time and O(1) space

• Suppose M=s.size() is the size of the string, for each character s[i], we need at most min(i,M-i) steps to find out the start and end locations of the longest palindrome centered at s[i]; and another at most min(i,M-i) steps to find out the start and end locations of the longest palindrome centered between s[i-1] and s[i]. All together, we need at most: 4*(1+2+...+M/2)=M^2/2+1, thus O(n^2) time. Only six size_t variables are used to store the start and end locations of the longest palindrome, current testing palindrome and a fake palindrome, thus O(1) for space.

``````class Solution{
public:
string longestPalindrome(const string& s){
if(s.empty())
return string();
const size_t strSize=s.size();
const size_t maxIdx = strSize-1;

//res_i0 and res_i1 are the start location
//and end location of the longest palindrome substring
//in s.
size_t res_i0=0,res_i1=0;

for(size_t i=1; i<strSize; ++i){
//start from s[1], since s[0] has already been stored
//by res_i0 and res_i1

for(size_t offset = 0; offset<2; offset++){
//offset = 0: this palindrome centers on s[i]
//offset = 1: this palindrome center between s[i-1] and s[i]
//word_i0 and word_i1 are the start and end location of
//current palindrome
size_t word_i0 = i-offset;
bool end_of_pal = (s[word_i0]!=s[i]);
size_t word_i1 = end_of_pal?word_i0:i;

//p0 and p1 is the expanded start and end location of
//current palindrome
size_t p0=word_i0,p1=word_i1;
while(!end_of_pal)
{
word_i0=p0;     //execute palindrome range expansion
word_i1=p1;     //execute palindrome range expansion
p0=word_i0-1;   //prepare for next expansion
p1=word_i1+1;   //prepare for next expansion
end_of_pal = (word_i0<=0) || (word_i1>=maxIdx);     //determine whether expasion is possible (note that unsigned integer word_i0 is not possible to be reduced to -1, thus we have to check the possibility of expansion here
if(!end_of_pal)
end_of_pal=(s[p0]!=s[p1]);      //determine whether the expanded substring is still a palindrome
}
if(word_i1-word_i0>res_i1-res_i0)
{
//compare current palindrome substring length with the length of the longest one
res_i0=word_i0;
res_i1=word_i1;
}
}
}
return s.substr(res_i0,res_i1-res_i0+1);
}
};``````

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