3. 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.

---

本题要求找出字符串中没有重复字母的最长连续子串。最快想到的是两重遍历i,j，每次用set判断是否重复，重复就进行下一次遍历i++，但是这样显然超时。 因为字符串中只有ASCII，所以可以用bool hash[128]来判断是否有重复字符，比set要快（用空间换时间）。
另外，假设遍历状态是abcdefgc，发现有两个’c’，下一次遍历的时候没必要从b开始遍历，因为从b开始肯定也会遇到后面的两个’c’，但此时字符串长度比之前的少1，所以可以直接从上次的’c’的下一个字母’d’开始重新遍历，这样可以节省不少时间。
完整代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        int longest = 0, n = s.size(), cur = 0;
        vector<int> hash(128, 0);
        for (int i = 0; i < n; i++) {
            if (hash[s[i]]) {
                if (cur > longest)
                    longest = cur;
                cur = 0;
                i = hash[s[i]]; //从重复字符下一个字符开始遍历
                //memset(&hash[0], 0, 128*sizeof(int));//比fill更快，但是没fill安全
                fill(hash.begin(), hash.end(), 0);
            }
            hash[s[i]] = i + 1; //记录下一个字符下标
            cur++;
        }
        return (longest > cur) ? longest : cur;
    }
};

本代码提交AC，用时68MS。
二刷，上面我的解法太过复杂。其实我们可以用一个map保存出现字符的最大下标，start保存一个下标，使得从start到当前字符这个区间不存在重复字符。
每来一个字符，我们去map中找一下，如果该字符之前存在，则更新start为最大下标（为了满足从start到当前字符这个区间不存在重复字符），然后不重复子串的长度就是i-start。
完整代码如下，因为s只包含字符，所以也可以用一个256长的数组表示map。

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        map<char, int> visited;
        int ans = 0, start = -1;
        for (int i = 0; i < s.size(); ++i) {
            if (visited.find(s[i]) != visited.end())
                start = max(start, visited[s[i]]);
            visited[s[i]] = i;
            ans = max(ans, i – start);
        }
        return ans;
    }
};

本代码提交AC，用时22MS。

三刷。首尾指针法，令[i,j)为不含重复字符的子串的区间，用一个hash数组存储某个字符是否出现过。开始的时候，j不断往前走，直到遇到区间[i,j)中出现过的字符，假设这个字符下标为k的话，则需要把[i,k]之间的hash全部重置为0，i跳到k+1，此后j继续往前走。

完整代码如下：

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int n = s.size();
		if (n == 0 || n == 1)return n;
		vector<int> hash(256, 0);
		int i = 0, j = 1;
		hash[s[0]] = 1;
		int ans = 0;
		while (j < n) {
			while (j < n&&hash[s[j]] == 0) {
				hash[s[j]] = 1;
				++j;
			}
			if (j - i > ans)ans = j - i;
			if (hash[s[j]] == 1) {
				while (s[i] != s[j]) {
					hash[s[i]] = 0;
					++i;
				}
				hash[s[i]] = 0;
				++i;
			}
		}
		return ans;
	}
};

本代码提交AC，用时8MS，虽然比解法2快，但解法2代码最简单了。