3. Longest Substring Without Rep

原题链接：Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.
Example 1:Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Example 2:Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:Input: "pwwkew" Output: 3 Explanation: 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.

看见without repeating characters，第一直觉是使用Collection来去重。（当然第一步应该是装个傻给面试官一个brute force solution，i.e.遍历所有的substring然后找到最长无重复字符串的解）且这道题比Minimum Window Substring简单一点的地方在于，它不需要返还substring，only maintain a global variable of the minimum length。

还是一个快指针慢指针。快指针向右移动同时将经过的character作为key，它对应的index作为value存进一个HashMap。只要没有遇到HashMap里存在的key，就一直移动并且更新maxLength。每当遇到一个HashMap里已有的key，就调取这个value，删除掉Map里所有在这个value之前的key，然后把慢指针移动到value对应的index，再更新HashMap里这个key的value。然后再把当前快指针和慢指针夹着的substring长度跟maxLength做比较。

Corner cases are fairly straightforward. Check null case. Check whether the string length is 0. Make sure that the slow pointer won't go over the fast pointer.

OK 这是一个写完之后我自己总隐隐觉得哪里不对但是AC了的版本。一开始总觉得for loop里的最后一步不对。后来用一个例子走了一遍流程之后想通了，思路写在了comment里。

class Solution {
    /**
     * Par exemple:"ababcbb"
        i = 0 => {<a,0>} maxLength = 1
        i = 1 => {<a,0>,<b,1>}, maxLength = 2
        i = 2 => 删掉a => {<a,2>,<b,1>} (maxLength没有被更新，好像问题不大，因为此时左指针移动了，此时的长度不可能比maxLength更大，不需要做比较)
        i = 3 => 删掉<b,1>, 再把最新的value放进去=>{<a,2>,<b,3>} (maxLength还是没有被更新)
        i = 4 => 加入<c,4> => {<a,2>,<b,3>,<c,4>}, maxLength = 3
        也就是说每次left pointer移动之后，都不需要检查maxLength。除非有新的元素被放进map，否则maxLength都不可能被更新。
    **/
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        char[] charS = s.toCharArray();
        int left = 0;
        int maxLength = Integer.MIN_VALUE;
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        
        for (int i = 0; i < charS.length; i++) {
            if (map.get(charS[i]) == null) {
                map.put(charS[i], i);
                
                // Should we update the maxLength?
                maxLength = Math.max(maxLength, i - left + 1);
                continue;
            }
            int location = map.get(charS[i]); // 当map里发现重复了，应该把从左指针到重复的index之间的character全都移除。左指针应该挪到出现重复的字符的下一个？
            while (left <= location) {
                map.remove(charS[left++]);
            }
            map.put(charS[i], i);
        }
        
        return maxLength;
    }
}

我自己写的这个版本没有严格按照网上找到的sliding window模板来。找了一个哥们儿的blog，感觉他的写法思路是一致的只是表现形式是反的：https://www.cnblogs.com/hygeia/p/6477177.html

改动了一下我的Revision#1，把判断条件反了一下，更接近模板的样子了：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        char[] charS = s.toCharArray();
        int left = 0;
        int maxLength = Integer.MIN_VALUE;
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        
        for (int i = 0; i < charS.length; i++) {
            if (map.get(charS[i]) != null) {
                int location = map.get(charS[i]);
                
                while (left <= location) {
                    map.remove(charS[left++]);
                }
            }
            map.put(charS[i], i);
            maxLength = Math.max(maxLength, i - left + 1);
        }
        
        return maxLength;
    }
}

但我个人其实是不喜欢这种写法的，纯粹是出于工业界的coding readability考虑。在窗口内的substring不满足判断条件的时候，需要用while循环来移动left pointer，也就意味着代码会出现三层indentation。这样的代码基本上是过不了我们组的code review的（笑）