Is this solution linear or quadratic?


  • 0
    W

    Although the system accept this solution and return a good runtime, I still this solution takes quadratic time in the worst case. When the input string is unique, the inside for loop will execute i-1 times every time, which means it will execute (n-1)+(n-2)+.....+1=(n-1)n/2 times. Is that right?

    public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(s == null) return 0;
        char[] str = s.toCharArray();
        if(str.length == 0) return 0;
        
    
        int max = 1;
        
        int barrier = 0;
    
        for(int i = 1; i < str.length; i++){
            for(int j = i - 1; j >= barrier;j--){
                if(str[i] == str[j]){
                    barrier = j + 1;
                    break;
                }
            }
            
            max = Math.max(max, i - barrier + 1);
        }
        
        
        return max;
        
    }
    

    }


Log in to reply
 

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