Java, O(n^2) time, O(1) space, 7ms, beats 78.33%, with explanation


  • 1
    K

    In this solution, I used two pointers (lo and hi) to find the longest substring starting at each position.

    Notice that we do not need to reset hi to the position of lo every time.

    For example:

    abcdbcdcdd
    ^^
    

    The carets mark the two pointers.

    We keep increasing hi until it has repeating characters:

    abcdbcdcdd
    ^   ^
    

    "abcdb" now has repeated characters.

    We only need to increase lo until there are no repeated characters:

    abcdbcdcdd
      ^ ^
    

    And then start the process all over again.

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n=s.length();
            if(n<2) return n;
            int lo=0,hi=0,max=0;
            char[] c = s.toCharArray();
            char curr;
            boolean ok;
            while(hi<n){
                while(hi<n){
                    curr = c[hi];
                    ok = true;
                    for(int i=lo;i<hi;i++){
                        if(c[i] == curr){
                            ok = false;
                            break;
                        }
                    }
                    if(!ok) break;
                    hi++;
                }
                if(hi-lo > max) max = hi-lo;
                lo++;
            }
            return max;
        }
    }

  • 0
    W

    So you're trading time for space, increasing the O(n) time of sliding window approach to O(n^2), decreasing space complexity from O(m) to O(1)


  • 0
    L
    This post is deleted!

Log in to reply
 

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