why my O(n^2) solution beats 99%?


  • 0
    Y
    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int max = 0;
            char[] s_array = s.toCharArray();
            if( s_array.length == 0 ){
                return 0;
            }
            int front = 0, end = 1;
            while( end < s_array.length ){
                for( int i = front; i < end; i++ ){
                    if( s_array[i] == s_array[end] ){
                        max = Math.max( max, end - front );
                        front = i + 1;
                        break;
                    }
                }
                end++;
            }
            max = Math.max( max, end - front );
            return max;
        }
    }
    

    Apparently it's a O(n2) solution, but the OJ gives 39ms runtime, beating 99%. Have no idea why.


Log in to reply
 

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