3 Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/?tab=Description

Given a string, find the length of thelongest substringwithout 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 asubstring,"pwke"is asubsequenceand not a substring.

代码 && 分析

第一年什么都不懂的时候面google碰到的，本也算是考官放我一马，无奈自己不争气，哭瞎

思路就是维持一个小窗口，两个指针，一个hashSet记录曾经遇到过的字母。

runner在到达字符串尾之前，
    如果当前字符是没有遇到的，就把这个字符添加进set
    如果当前字符遇到过：
        当前就是以该字母结束的可能的最长解，所以更新maxLen.
        那么就移动walker，目标是缩到第一个和当前字母不同的位置上(这样可能造成下一个最长的不同字母字符串)，
            那么我们把walker位置上的字母从set里面移去
最后返回maxLen和(runner - walker)比较大的那个

代码如下：

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int maxLen = 1;
        int walker = 0;
        int runner = 0;
        Set<Character> seen = new HashSet<>();
        while (runner < s.length()) {
            char curChar = s.charAt(runner);
            if (seen.contains(curChar)) {
                maxLen = Math.max(maxLen, runner - walker);
                while (s.charAt(walker) != curChar) {
                    seen.remove(s.charAt(walker));
                    walker++;
                }
                walker++;//注意，walker要多补一位
            } else {
                seen.add(curChar);
            }
            runner++;
        }
        return Math.max(runner - walker, maxLen);//最后一组可能是最优解，但是没有更新进去，这里需要检查
    }

时间复杂度O(n)

用模板做：

https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems/2

public int lengthOfLongestSubstring(String s) {
    if(s == null) {
        return 0;
    }
    int[] map = new int[128];
    int cnt = 0;
    int len = s.length();
    int start = 0;
    int end = 0;
    int maxLen = 0;
    while(end < len) {
        if(map[s.charAt(end++)]++ > 0) {
            cnt++;
        } 
        while(cnt > 0) {
            if(map[s.charAt(start++)]-- > 1) {
                cnt--;
            }
        }
        maxLen = Math.max(end - start, maxLen);
    }
    return maxLen;
}