[Java] 20 lines solution with explanation


  • 1
    L

    Two indexes will traverse the String from left to right. We are interested in the substring between left/right index.

    The loop keeps increasing the right index by 1. if character at right index repeats in this substring, then increase left index until no repeated characters exists.

    For example,

                       maximun length
    LR 
    abcadb       2
    
    L_R
    abcadb       3
    
    L__R
    abcadb       "a" repeat
    
    _L_R
    abcadb       3
    
    _L__R
    abcadb       4
    
    _L___R
    abcadb       "b" repeat
    
    __L__R
    abcadb       4
    
    __L____R
    abcadb        halt
    
    
    
       public class Solution {
            public int lengthOfLongestSubstring(String s) {
                int left=0,right=0,max=0;
                HashSet<Character> map = new HashSet<Character>();
                while(right<s.length()){
                    if(map.contains(s.charAt(right))){
                        max = Math.max( max, right - left);
                        while(s.charAt(left)!=s.charAt(right)){
                            map.remove(s.charAt(left++)); 
                        }
                        ++left;
                    } 
                    else map.add(s.charAt(right));
                    ++right;
                }
                max = Math.max( max, right - left);
                return max;
            }
        }

Log in to reply
 

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