Accepted O(N^3) with Pruning

  • 0

    Hey, I tried this problem and got TLE (I was using O(N^3) algo), then I tweaked my inner loop to do some pruning, as follows:

    class Solution {
        string longestPalindrome(string s) {
            int len = s.length();
            string ret;
            int maxlen = 0;
            for(int i = 0;i<len;i++){
                for(int j = len-1;j>=i;j--){
                    // If the length of longest current result is longer than what is to be checked, skip it.
                    if(maxlen > j-i+1)continue;
                    int temp_i,temp_j;
                    temp_i = i;
                    temp_j = j;
                    bool valid = true;
                    while(temp_i < temp_j){
                        if(s[temp_i] != s[temp_j]){
                            valid = false;
                        if(maxlen < j-i+1){
                            maxlen = j-i+1;
                            ret = s.substr(i,maxlen);
            return ret;

    IMO my solution shouldn't be allowed to pass and you can consider adding test cases to account for this kind of solutions!

    Good day! :)

Log in to reply

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