3. Longest Substring Without Repeating Characters

求出一个string中最长的没有重复字符的子串。

还是比较简单的，直觉上感觉遍历一次就可以，依次判断string中的每个字符之前是否出现过（所以需要一个Set）；还需要记录当前已经出现过的所有非重复字符，当出现重复字符时，把重复字符之前所有的字符都丢掉（所以需要一个Queue）。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 注意边界条件的判断，leetcode的test case中很多用于坑爹的corner case。。。
        if (s == null || s.trim().length() == 0) {
            return 0;
        }

        Set<Character> set = new HashSet<Character>();  // 用于判断一个字符是否出现过
        Queue<Character> queue = new LinkedList<Character>();  // 保存包括当前字符并且无重复字符的最大子串

        int max = 0;
        for (int i = 0; i < s.length(); i++) {   // 遍历string
            char thisChar = s.charAt(i);  // 当前字符
            if (set.contains(thisChar)) {
                // 如果当前字符是已经出现过的，就把这个字符上次出现之前的所有字符都丢掉，这样queue中剩下的就是包括当前字符的、无重复字符的最大子串
                max = Math.max(max, queue.size());
                while (queue.size() > 0) {
                    char tmp = queue.poll();
                    if (tmp == thisChar)
                        break;
                    else
                        set.remove(tmp);   // 别忘了移除set中的元素，set中的元素和queue是一致的
                }
                queue.add(thisChar);
            } else {
                set.add(thisChar);
                queue.add(thisChar);
            }
        }

        return Math.max(max, queue.size());
    }
}