3. Longest Substring Without Repeating Characters

Hash Table + greedy(or two-pointers?)

定义三个变量

• start: 上一个end+1和当前的start取最大值（为啥取最大值是为了维护当前的状态，如果当前end指向一个表中没有被记录过的字符，那么start会变成0，这样不对）
• end: loop字符串的index
• res: 最长长度

一次遍历，使用一个hashtable<character, index>记录每个字母最近出现的index。start代表的是最近一个没有重复的字母出现的位置，如abca，当指针指向第二个a的时候，取出来的index为1，代表从b开始的字符串。然后计算end - start + 1的意思就是bca字符串的长度。

之所以要这样写，而不是写成end-start, index[s.charAt(end)] = end的原因是，当字符串不存在重复字符时，要将当前指针指向的字符串算入。

public int lengthOfLongestSubstring(String s) {
    int length = s.length();
    int res = 0;
    int[] index = new int[256];
    int start = 0;
    for (int end = 0; end < length; end++) {
        start = Math.max(start, index[s.charAt(end)]);
        res = Math.max(res, end - start + 1);
        index[s.charAt(end)] = end + 1; // 最近一个不重复数字的index
    }
    return res;
}

13.07.2019 updated..

频率数组+双指针法

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) return 0;
    int[] index = new int[128];
    int res = 0, i = 0, j = 0;
    while (i < s.length()) {
        if (j < s.length() && index[s.charAt(j)] == 0) {
            index[s.charAt(j)]++;
            j++;
            res = Math.max(res, j - i);
        } else {
            index[s.charAt(i)]--;
            i++;
        }
    }
    return res;
}

应用：分割成非重复单元 --> 有啥用？寻找没有重复字母出现的单词？数字？基因序列AGCT？不知道哇