I think the time complexity of my solution is O(n^2). Why it exceeded time limit?


  • 0
    E
    public class Solution {
        public String longestPalindrome(String s) {
            if(s.length() < 2) return s;
            int maxStart = 0;
            int maxEnd = 0;
            for(int i = 1; i < s.length(); i++){
                if(i < s.length() -1 && s.charAt(i-1) == s.charAt(i+1)){
                    int start = i-2;
                    int end = i+2;
                    while(end < s.length() && start >= 0){
                        if(s.charAt(start) == s.charAt(end)){
                            start--;
                            end++;
                        }
                        else break;
                    }
                    start++;
                    end--;
                    if(end - start > maxEnd - maxStart) {
                        maxStart = start;
                        maxEnd = end;
                    }
                    
                }
                 if(s.charAt(i) == s.charAt(i-1)){
                    int start = i-2;
                    int end = i+1;
                    while(end < s.length() && start >= 0){
                        if(s.charAt(start) == s.charAt(end)){
                            start--;
                            end++;
                        }
                        else break;
                    }
                    start++;
                    end--;
                   if(end - start > maxEnd - maxStart) {
                        maxStart = start;
                        maxEnd = end;
                    }
                }
                
            }
            return s.substring(maxStart, maxEnd+1);
        }
    }
    

  • 0

    @Eternal But actually it can be easily solved in O(n) instead of O(n^2), so try harder on this.


  • 0

    @LHearen Which way are you thinking of? I don't know an easy O(n) one. And I think the three top-voted answers also are only O(n^2), not O(n).

    @Eternal I just submitted it five times, every time it got accepted. With times 96 ms to 116 ms. And the slowest accepted solution shown in the distribution graph took 240 ms. Are you sure you got "Time Limit Exceeded"?


  • 0
    E

    @StefanPochmann Thx. It works now. Don't know why it didn't work yesterday.


  • 0
    E

    @LHearen Thx, will work the O(n) solution.


  • 0

    @StefanPochmann @Eternal Sorry, my mistake. But indeed, your solution is little bit complicated. Here is my cleaner solution O(n^2) as yours, in C++.

    
    class Solution {
    public:
        string longestPalindrome(string s) 
        {
            int sLen = s.length(), maxLen = 0, maxStart = 0;
            int i = 0, l = 0, r = 0, len = 0;
            while(i<=sLen-maxLen/2)
            {
                l = r = i;
                while(r<sLen-1 && s[r+1]==s[r]) r++;
                i = r+1;
                while(l>0 && r<sLen-1 && s[r+1]==s[l-1]) l--, r++;
                len = r-l+1;
                if(maxLen < len) maxLen = len, maxStart = l;
            }
            return s.substr(maxStart, maxLen);
        }
    };
    

  • 0

    Well the solution above is cleaner, but I have to say it is easier to understand the longer one. And that Java code is accepted with 36 ms.


Log in to reply
 

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