Leetcode - 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.
[分析] 下面给出的两种方法基本思路一致，使用两指针表示滑动窗口的左右边界，窗口中的
字符均不重复。若遇到新字符，右指针往前走，若遇到窗口中已有字符，寻找窗口中该字符的下标idx，左指针移到idx下一个位置。方法1是O(n^2)，方法2是O(n)的， 方法2的高效之处在于使用一个table保存了所遇字符上一次的出现位置，因此可以在单位时间内完成更新左指针操作。

    // Method 2 : 开一个字符集大小的数组存储遍历s时遇到的字符的最近一次位置，
    //相较Method 1, 节省了寻找上次出现位置以及从HashSet删除新窗口外的字符操作开销
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int n = s.length();
        int max = 0;
        int[] lastPosTable = new int[256];
        for (int i = 0; i < 256; i++)
            lastPosTable[i] = -1;
        int i = 0, j = 0;
        while (j < n) {
            int lastPos = lastPosTable[s.charAt(j)];
            if (lastPos >= i) {
                max = Math.max(max, j - i);
                i = lastPos + 1;
            }
            lastPosTable[s.charAt(j)] = j;
            j++;
        }
        return Math.max(max, j - i);
    }
    
    // Method 1: Brute force, time out
    // 2 pointer, characters in the sliding window are distinct 
    // which store in the hashset
    public int lengthOfLongestSubstring1(String s) {
        if (s == null || s.length() == 0)
            return 0;
        HashSet<Character> set = new HashSet<Character>();
        int i = 0, j = 0;
        int max = 0;
        int n = s.length();
        while (j < n) {
            char curr = s.charAt(j);
            if (set.contains(curr)){
                max = Math.max(max, set.size());
                while (i < j && s.charAt(i) != curr) {
                    set.remove(s.charAt(i++));
                }
                set.remove(s.charAt(i++));
            }
            set.add(curr);
            j++;
        }
        return Math.max(max, set.size());
    }