Why Time Limit Exceeded Error for this code?


  • 0
    E

    Here comes the code:

    public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int L = s.length();
        if(L<=1) return L;
        
        int max = 1;
        HashMap<Character, Integer> map = new HashMap<>();
        int i = 0;
        while(i<L) {
            map.clear();
            char ch1 = s.charAt(i);
            map.put(ch1, i);
            int a, b, b1, b2, j;
            a = b = b1 = b2 = 0;
            j = i+1;
            while(a==0 && b1==0 && b2==0 && j<L) {
                char ch2 = s.charAt(j);
                if(map.containsKey(ch2)) {
                    if(ch2!=ch1 && b==0) {
                        a = 1;
                        max = j-i > max ? j-i : max;
                        i = map.get(ch2) + 1;
                    }
                    else if(ch2==ch1 && b==0) {
                        b = 1;
                        map.replace(ch1, j);
                    }
                    else if(ch2!=ch1 && b!=0) {
                        b1 = 1;
                        max = j-i-1 > max ? j-i-1 : max;
                        i = map.get(ch2) + 1;
                    }
                    else {
                        b2 = 1;
                        max = j-i-1 > max ? j-i-1 : max;
                        i = map.get(ch1) + 1;
                    }
                }
                else {
                    map.put(ch2, j);
                    max = j-i+1 > max ? j-i+1 : max;
                }
                j++;
            }
            if(j>=L) i = L;
        }
        return max;
    }
    

    }

    It fails the following input with TLE error:

    "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ ... 
    

    the whole string is too long to put here...

    However, when I run with this input, it is able to finish with 95ms. Is it because this algorithm is O(n^2) in the worst case? But it is almost O(n) for the above string as I tried to double the above string and the running time is almost doubled.


  • 0
    H

    I also encounter Time Limite Exceeded Error when running this case. And I wrote in C++.


Log in to reply
 

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