# MLE and now TLE: Longest Palindromic Substring

• I wrote an `O(n^2)` DP code for this problem:

``````string longestPalindrome(string s) {
if(s.length() < 2) return s;

// dp[i][j] denotes the longest substring length from i to j
vector<vector<int> >  dp(s.length(), vector<int>(s.length(), 0));
int n = s.length();
int start = 0, end = 0, Max = 1;
for(int i = n - 1; i >= 0; --i) {
dp[i][i] = 1;
for(int j = i + 1; j < n; ++j) {
dp[i][j] = (s[i] == s[j] and (j - i < 3 or dp[i + 1][j - 1] == j - 1 - i))
? dp[i + 1][j - 1] + 2
: max(dp[i][j - 1], dp[i + 1][j]);
if(dp[i][j] > Max) {
Max = dp[i][j];
start = i, end = j;
}
}
}
return s.substr(start, end - start + 1);
}
``````

This gave Memory Limit Exceeded. Then I realize the `vector<vector<int> > dp(s.length(), vector<int>(s.length(), 0))` declaration causes this. Then I change it a bit to avoid the extra space.

``````string longestPalindrome(string s) {
if(s.length() < 2) return s;

// dp[i][j] denotes whether string i...j is palindrome or not
vector <vector<bool> > dp(s.length(), vector<bool>(s.length(), false));
int start = 0, maxLen = 1;
int n = s.length();
for(int i = n - 1; i >= 0; --i) {
dp[i][i] = true;
for(int j = i + 1; j < n; ++j) {
dp[i][j] = (s[i] == s[j] and (j - i < 3 or dp[i + 1][j - 1])) ? true : false;
if(dp[i][j]) {
int len = j - i + 1;
if(len > maxLen) {
maxLen = len;
start = i;
}
}
}
}
return s.substr(start, maxLen);
}
``````

Now the Memory Limit Exceeded but I got Time Limit Exceeded for this input:

``````"flsuqzhtcahnyickkgtfnlyzwjuiwqiexthpzvcweqzeqpmqwkydhsfipcdrsjkefehhesubkirhalgnevjugfohwnlhbjfewiunlgmomxkafuuokesvfmcnvseixkkzekuinmcbmttzgsqeqbrtlwyqgiquyylaswlgfflrezaxtjobltcnpjsaslyviviosxorjsfncqirsjpkgajkfpoxxmvsyynbbovieoothpjgncfwcvpkvjcmrcuoronrfjcppbisqbzkgpnycqljpjlgeciaqrnqyxzedzkqpqsszovkgtcgxqgkflpmrikksaupukdvkzbltvefitdegnlmzeirotrfeaueqpzppnsjpspgomyezrlxsqlfcjrkglyvzvqakhtvfmeootbtbwfhqucbnuwznigoyatvkocqmbtqghybwrhmyvvuchjpvjckiryvjfxabezchynfxnpqaeampvaapgmvoylyutymdhvhqfmrlmzkhuhupizqiujpwzarnszrexpvgdmtoxvjygjpmiadzdcxtggwamkbwrkeplesupagievwsaaletcuxtpsxmbmeztcylsjxvhzrqizdmgjfyftpzpgxateopwvynljzffszkzzqgofdlwyknqfruhdkvmvrrjpijcjomnrjjubfccaypkpfokohvkqndptciqqiscvmpozlyyrwobeuazsawtimnawquogrohcrnmexiwvjxgwhmtpykqlcfacuadyhaotmmxevqwarppknoxthsmrrknu"
``````

So is this `O(n^2)` algorithm is time consuming for this problem? Should I seek for a faster algorithm?

• Well, I found a solution in leetcode blog of `O(n^2)` with constant space and got Accepted:

``````   string expandAroundCenter(string s, int c1, int c2) {
int l = c1, r = c2;
int n = s.length();
while (l >= 0 and r < n and s[l] == s[r]) {
l--;
r++;
}
return s.substr(l + 1, r - l - 1);
}

string longestPalindrome(string s) {
int n = s.length();
if (n < 2) return s;
string longest = s.substr(0, 1);  // a single char itself is a palindrome
for (int i = 0; i < n - 1; i++) {
string p1 = expandAroundCenter(s, i, i);
if (p1.length() > longest.length())
longest = p1;

string p2 = expandAroundCenter(s, i, i + 1);
if (p2.length() > longest.length())
longest = p2;
}
return longest;
}``````

• @kaidul This is just fixed. Now your solution gets Accepted.

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