MLE and now TLE: Longest Palindromic Substring


  • 1
    K

    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?


  • 1
    K

    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;
        }

  • 0

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


Log in to reply
 

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