Leetcode 3 @ Java @ CONY的世界

3. 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 subsequenceand not a substring.

這題不是用DP，因為一但遇到重疊的基本上counting是直接歸零

看解答也是用two pointer 掃過所有可能，l 負責記錄開頭，r 負責記錄結尾，

用兩個紀錄的好處是當要清除重複的字元時，前面非重複字元其實也要從set清除掉，

所以 l 可以幫助紀錄到底需要清掉哪些字元，中間過程中我們會掃過所有可能的不重複字串，

所以要有一個int 去記錄這之中最長的字串在最後return

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int r=0, l=0, max=0;
        HashSet<Character> set = new HashSet();
        while(l < s.length()){
            if(!set.contains(s.charAt(l))){
                set.add(s.charAt(l++));
                max = Math.max(max,set.size());
            } else
                set.remove(s.charAt(r++)) ;          
        }
        return max;
    }
}