# This solution is simple but timed out for a long "aaaaaaaaaa...........bc...aaaa" string?

• This solution is simple but time out for a long "aaaaaaaaaa...........bc...aaaa" string.

``````class Solution {
public:
string longestPalindrome(string s) {

string ret;
map<int,int> ms;

int sz=s.size();
if(sz<=1) return s;
if(sz==2)
{
if(s[0]==s[1]) return s;
else return s.substr(0,1);
}
ms.insert(pair<int,int>(1,0));

for(int i=0;i<sz;i++)   //search starts from the beginning
{
for(int j=sz-1;j>i;j--) //search range from the end then backwards
{
if(p(s,i,j))
{
ms.insert(pair<int,int>(j-i+1,i));
break;  //once found, search starts from the next beginning
}
}
}

map<int,int>::reverse_iterator it = ms.rbegin();
return s.substr(it->second,it->first);
}

bool p(string s, int start, int end)
{
//is this range a palin?
int sz=end-start+1;
string sub=s.substr(start,sz);

for(int i=0;i<sz/2;i++)
{
if(sub[i]!=sub[sz-1-i])
return false;
}
return true;
}
};``````

• use array not map or vector then accept

• I did the exact same thing, but with array and its still timing out for the string mentioned in the post.

• This is an O(n^3) algorithm, oj is looking for O(n^2)

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