引子

这道题可以用暴力的方法,遍历枚举所有的子串，如果子串没有重复元素，则更新max，但是时间复杂度很高，最后超时了。看到讨论区的算法：

int lengthOfLongestSubstring(string s) {
    map<char, int> charMap;
    int j = 0;
    int maxLen = 0;
    for (int i = 0; i < s.size(); i++) {
        if (charMap.count(s[i]) != 0) {
            j = max(j, charMap[s[i]]+1);
        }
        charMap[s[i]] = i;
        maxLen = max(maxLen, i-j+1);
    }
    return maxLen;
}

作者解释：

the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.

该作者只解释了这个算法是如何操作的，但却没有说明为什么算法是「正确」的，我晚上看了一下，不是很懂算法的正确性如何证明。早上起来继续想，终于想通了，尝试把这个算法用我这种小白能够理解的语句来进行描述和分析如下。

解决方法

定义s[i]为以位置i的字符结尾的最大不重复子串，则：

1.如果str[i]不在s[i-1]里
    s[i] = s[i-1] ++ str[i] (++为连接符)
2.否则
    s[i] = 以s[i-1]中str[i]的后一个位置起始，以位置i的字符为结束的子串  

怎么想到的呢，我们这样来思考。从数组的第一个元素为子串的起始位置和结束位置，设j指向开始位置，i指向结束位置，那么当i在遍历的过程中，在遇到重复的元素之前，子串是一直增长的；当i=k的时候，如果遇到元素s[k]与子串s[j,k-1]中的元素有重复，这个时候将j移动到子串s[j,k-1]里重复的元素的下一个位置，则子串s[j,i]仍然是以位置i的字符结束的最大子串。也就是说，只要新考察的那个字符是重复的，就修改当前子串的起始位置为上一次该重复字符在子串中出现位置的下一位，这种修改保证了新子串一定是以该重复字符为结尾的最大子串。因为我弱，所以才啰嗦这么多:)

那么我自己就可以实现这个算法了呀:

int lengthOfLongestSubstring(string s) {
    int start = 0, end = 0, maxLen = 0, ascii[256];//ascii最多256个字符
    memset(ascii, -1, 256 * sizeof(int));//初始化为-1是为了防止第2个元素就重复了
    for (end = 0; end < s.length(); end++) {
        if (ascii[s[end]] >= start) start = ascii[s[end]] + 1;
        if (end - start + 1 > maxLen) maxLen = end - start + 1;
        ascii[s[end]] = end; //记录最后一次s[end]出现的位置
    }
    return maxLen;
}

另一个解决方案

见Minimum Window Substring

int lengthOfLongestSubstring(string s) {
    int ascii[256];
    memset(ascii, 0, 256 * sizeof(int));
    int start = 0, end = 0, count = 0, maxCount = 0;
    while (end < s.length()) {
        ascii[s[end]]++;
        count++;
        while (ascii[s[end]] > 1) { // 如果发现重复元素
            ascii[s[start++]]--; // start后移直到无重复元素
            count--;
        }
        if (count > maxCount) maxCount = count;
        end++;
    }
    return maxCount;
}

附

一开始不理解，做的算法运行状态模拟如下：

--------------
str: abcadaebf
j:   ↑
i:   ↑
--------------
str: abcadaebf
j:   ↑
i:    ↑
--------------
str: abcadaebf
j:   ↑
i:     ↑
--------------
str: abcadaebf 更新j
j:    ↑
i:      ↑
--------------
str: abcadaebf
j:    ↑
i:       ↑
--------------
str: abcadaebf 更新j
j:       ↑
i:        ↑
--------------
str: abcadaebf
j:       ↑
i:         ↑
--------------
str: abcadaebf
j:       ↑
i:          ↑
--------------
str: abcadaebf
j:       ↑
i:           ↑