Getting TLE for an O(n^2) solution of Longest Palindromic Substring
293
I solved the Longest Palindromic Substring problem using dynamic programming approach with property dp[i][j]=s[i]+dp[i+1][j-1]+s[j] if s[i]==s[j] etc.
My code gives Time Limit Exceeded even though the most optimal solution given is also O(n^2) and my algorithms time complexity is 1+2+......+n-1 = O(n^2). When I run the code provided in solutions (which is again O(n^2), it doesn't give TLE.
I am pasting my code. Can someone please explain why this happens? Please let me know what mistake I am making.
int n=s.size();
//cout<<n<<endl;
if(n==0)
return "";
string dp[n][n];
for(int j=0;j<n;j++)
{
for(int i=j+1;i<n;i++)
{
dp[i][j]="";
}
}
for(int i=0;i<n;i++)
{
dp[i][i]=s[i];
}
int maxall=-1;
string ans="";
for(int i=n-2;i>=0;i--)
{
for(int j=i+1;j<n;j++)
{
if(i+1>j-1)
{
if(s[i]==s[j])
{
string temp="";
temp+=s[i];
temp+=s[j];
dp[i][j]=temp;
}
else
{
dp[i][j]="";
}
}
else
{
if(dp[i+1][j-1]=="" || s[i]!=s[j])
{
dp[i][j]="";
}
else
{
//dp[i][j]="";
dp[i][j]=s[i]+dp[i+1][j-1]+s[j];
}
}
int m=dp[i][j].size();
if(m>maxall)
{
maxall=m;
ans=dp[i][j];
}
}
}
if(ans=="")
{
ans+=s[0];
}
return ans;Comments (1)