# O(N^2) solution with no extra space. C++. Divide the solution into two cases. Any improvement?

• Similar to the idea at the bottom of this leetcode page, we divide the solution into two cases:

(1) palindromic substring with one letter as the middle point

(2) palindromic substring with the center between two letters as the middle point

``````class Solution {
public:
string longestPalindrome(string s) {
if (s.size()==0)
return "";

// Base case: there is just one letter in the string
int maxLength= 1 ;
string result=s.substr(0,1);

for (int i =0; i<s.size()-1; i++) {
// substring with the letter as the middle point
int count = 0;
while (i-count>=0 && i+count<=s.size()-1) {
if (s[i-count]==s[i+count])
count++;
else
break;
}
count--;
if (count*2+1>=maxLength) {
maxLength = count*2+1;
result = s.substr(i-count,count*2+1);
}

// substring with the center between two letters as the middle point
int count2 = 0;
while (i-count2>=0 && i+count2+1<=s.size()-1) {
if(s[i-count2]==s[i+1+count2])
count2++;
else
break;
}
if(count2*2>=maxLength) {
maxLength = count2*2;
result = s.substr(i+1-count2, count2*2);
}
}
return result;

}
};
``````

• There is a Manacher's algorithm, it's a linear time algorithm

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