最长不含重复字符的子字符串（C++）

  请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

数据范围：s.length≤40000

输入：
"abcabcbb"
返回值：
3
说明：
因为无重复字符的最长子串是"abc"，所以其长度为 3。

输入：
"bbbbb"
返回值：
1
说明：
因为无重复字符的最长子串是"b"，所以其长度为 1。

输入：
"pwwkew"
返回值：
3
说明：
因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。 

每一个字符都比较与该字符前面字符是否重复，相同则更新起始标记位，同时每遍历一个字符都要获取当前的最长子字符串。

class Solution {
  public:
    
    int lengthOfLongestSubstring(string s) {
        // write code here
        if (s.size() == 0) {
            return 0;
        }
        int max = 1, begin = 0;

        for (int i = 0; i < s.size(); i++) {
            for (int j = begin; j < i; j++) {
                if (s[j] == s[i]) {
                    begin = j + 1;
                }

            }
            if (i - begin + 1 > max) {
                max += 1;
            }
        }
        return max;
    }
};

用一个容器存储字符的位置所在，同时设置两个标记位，分别指向当前不重复子字符串的起始位置以及当前遍历位置。遍历字符串的时候，如果发现之前出现过该字符，那么应该更新起始标记位，而且其实标记位必须在该重复字符的后一位置（注意，起始位置只能前进，不能往后退，所以需要判断一下大小），最后通过res获取整个字符串的最大子字符串。

class Solution {
public:
    
    int lengthOfLongestSubstring(string s) {
        if(s == " " || s.length() == 1)return 1;
        if(s.empty())return 0;
        vector visited(4000,0);
        int res = -1;
        int start = 0,end = 1;
        while(end < s.length())
        {
            if(s[start] == s[end])
                start++;
            else if(visited[s[end]] != 0)
            {
                if(start < visited[s[end]]+1)
                    start = visited[s[end]] + 1;
            }
            visited[s[end]] = end; 
            end++;
            if(end - start > res)
                res = end - start;
        }
        return res;
    }
};