Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

这道题用的方法是在LeetCode中很常用的方法，对于字符串的题目非常有用。

此类方法基本思想是维护一个窗口，每次关注窗口中的字符串，左窗口和右窗口选择一个向前移动。用left和right表示窗口的左右边界，窗口中是不重复的字符串，正常情况下移动右窗口right，set中存放的是窗口中的字符，也就是子串的字符，当right向右移一个指向一个新字符时，看看set中是否存在此字符，如果不存在，则right继续向前移一位，并比较max和窗口的大小，如果窗口长度大于max表示该子串长度大，更新max。当set中存在此新字符时，就要移动左窗口left了，将它移到重复元素位置的后一位，重新开始新的窗口。具体见代码

public int lengthOfLongestSubstring(String s) {
        if(s==null||s.length()==0) return 0;
        HashSet<Character> set=new HashSet<>();
        int max=0;
        int left=0;
        int right=0;
        while(right<s.length()){
            //集合中不存在右窗口元素时，将右窗口元素加入集合并继续右移
            if(!set.contains(s.charAt(right))){
                set.add(s.charAt(right));
                right++;
            }else{
                /*当右窗口移到的新元素在set中以及存在了，说明此时的窗口已经不是最大子串了，需要将left右移，移到重复的元素后。并删除set中前面的 元素（保证set中只存放窗口的元素）
                */
                if(right-left>max)//此时right指向新元素
                    max=right-left;
                
                //移动left，找到重复的元素
                while(s.charAt(left)!=s.charAt(right)){
                    set.remove(s.charAt(left));
                    left++;
                }
                //上面循环找到了重复元素，left指向的就是重复元素，所以还得继续将left移一位
                left++;
                //上面没有删除重复的元素，因为right指向的重复元素没有加入set中，所以就不用删了，直接右移right
                right++;
            }
        }
        max=Math.max(max,right-left);
        return max;
    }