3. Longest Substring Without Repeating Characters (Medium) Amazon Bloomberg Yelp Adobe

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.

最长无重复子串

Solution 1: Brute-Force O(n^2); O(1)

这题同样可以用暴力搜索解决，i从0开始，j从i开始，注意这里j不是从i+1开始，因为要从i开始标记字符已经出现。

    public int lengthOfLongestSubstring(String s) {
        int maxLen =  0;
        for (int i = 0; i < s.length(); i++) {
            boolean[] isRepeat = new boolean[256];
            int j;
            for (j = i; j < s.length() && !isRepeat[s.charAt(j)]; j++) {
                isRepeat[s.charAt(j)] = true;
            }
            maxLen = Math.max(maxLen, j - i);
        }
        return maxLen;
    }

Solution 2: HashMap + Two Pointers O(n); O(n)

因为这题要求最大长度，实际上就是求最长无重复子串的开始和结束索引，所以可以联想到Two Sum。
引入HashMap，key是字符，value是索引，但这里key是字符，最大范围是256，所以可以用数组代替HashMap。
另外用Two Pointers维持一个滑动窗口，如果j处字符重复，更新i；每次都更新j处字符对应的索引。
下面第一个解法是以-1为map数组初始值，第二个是0。

    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        int[] map = new int[256];
        Arrays.fill(map, -1);
        for (int i = 0, j = 0; j < s.length(); j++) {
            i = map[s.charAt(j)] > -1 ? Math.max(i, map[s.charAt(j)] + 1) : i;
            map[s.charAt(j)] = j; 
            maxLen = Math.max(maxLen, j - i + 1);
        }
        return maxLen;
    }

    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        int[] map = new int[256];
        for (int i = 0, j = 0; j < s.length(); j++) {
            i = map[s.charAt(j)] > 0 ? Math.max(i, map[s.charAt(j)]) : i; //map[s.charAt(j)]不用+1
            map[s.charAt(j)] = j + 1; //j要+1
            maxLen = Math.max(maxLen, j - i + 1);
        }
        return maxLen;
    }