[Leetcode] Longest Substring without repeating characters

Longest Substring without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

two pointers,

1. hashset to store the character set of the current substring

2. left (int) points to the start of the substring

3. right (int) points to the end of the substring

4. max (int) store the current max length

both pointers start from 0

right move to the right, and if

1. found a duplicate, calculate the cur len, update the max length if necessary, and left++

2. no duplicate, then add cur character to set, right++

ending condition of the while loop is when right == s.length()

edgecase:

s == null   -> 0

s isEmpty  -> 0

??the longest substring ending at the last character, then we need to compute the length again outside the while loop

    public int lengthOfLongestSubstring(String s){
        if(s == null || s.isEmpty()) return 0;
        int max = 0;
        HashSet<Character> set = new HashSet<Character>();
        int left = 0, right = 0, n = s.length();
        while(right < n){
            if(set.contains(s.charAt(right))){
                int curLen = right-left;
                max = Math.max(max, curLen);
                while(s.charAt(left)!=s.charAt(right)){
                    set.remove(s.charAt(left));
                    left++;
                }
                left++;
                right++;
            }
            else{
                set.add(s.charAt(right));
                right++;
            }
        }
        max = Math.max(right-left, max);
        return max;
    
    }

[Leetcode] Longest Substring without repeating characters

原文：http://www.cnblogs.com/momoco/p/4848168.html