O(n) Java solution using Set


  • 0
    A

    Assuming a perfect hash function this is O(n) solution. The Set is actually used like a sliding window.

    Simple logic is

    1. Have two pointers start and end. Initially start = 0 and end =1;
    2. Add end to set. Increment end and check if set size == end-start.
    3. If yes and update max variable.
    4. If not then increment start will set size = end-start

    Be careful of certain corner cases like "aab", "a" "aa" etc.

    public static int lengthOfLongestSubstring(String s) {
        
        if(s.length()<=1) { return s.length();} 
        Set<Character> set = new HashSet<>(); 
    	
        int start = 0;
        int end = 1; 
        int max = 1; 
        set.add(s.charAt(start));
        while(end < s.length()){
            set.add(s.charAt(end));
            //System.out.println("Set is "+set); 
            max = Math.max(set.size(),max); 
            end++;
            //System.out.println("Set Size = "+set.size()+"\t"+(end-start)); 
            while(set.size()<(end-start)){
               if(s.charAt(start)!=s.charAt(end-1)){
                set.remove(s.charAt(start));
               }
                start++; 
               //System.out.println("Moving start : Set Size = "+set.size()+"\t"+(end-start)+"\t"+set); 
            }
         // System.out.println("Start is "+start); 
           //  System.out.println("End is "+end); 
        }
        
        return max; 
        
    }

Log in to reply
 

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