# A O(n^2) solution. whyt got "Time Limit Exceeded" in C++

• l use dp method to slove the problem, an array is used to store the status if i to j is Palindromic Substring ,
in the for loop lt take o(n^2) times ,but why still get "time limit exceeded" on test case "aaaaaa....aaa"
could the admin not close my post?

{

``````//dp from top to down
string longestPalindrome(string s) {
int nsize=s.length();
if(nsize<=1){
return s;
}
bool vec[1001][1001];
for(int i=0;i<nsize;i++){
for(int j=0;j<nsize;j++){
if(i==j)
vec[i][j]=true;
else
vec[i][j]=false;
}
}
int max=0;
int maxidx=-1;
for(int i=nsize-1;i>=0;i--){
for(int j=nsize-1;j>i;j--){
if((j-i)==1){
vec[i][j] = s[i]==s[j];
}else{
vec[i][j] = ((s[i]==s[j])&&vec[i+1][j-1]);
}
if(vec[i][j]==true&&(j-i+1)>max){
max=j-i+1;
maxidx=i;
}
}

}
if(maxidx!=-1&&max>0)
return s.substr(maxidx,max);
else
return "";
}
``````

}

• Just change the first O(n^2) loop to O(n)

``````for(int i=0;i<nsize;i++){
vec[i][i]=true;
}``````

• use memset to set vec to all 0

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