求不重复子字符串的最大长度

求不重复子字符串的最大长度

• 例子：
• Given ==”pwwkew”==, the answer is ==”wke”==, with the length of ==3==.

my Solution:

1. 设置一个128长度的数组，作为每个字符是否出现过的标志位，-1表示没出现过，i表示该字母出现在字符串的第i位。
2. 遍历字符串，若该字符标志位为-1，则长度加一，若不为-1，则转到step3.
3. 清空无法使用的字符的标志位为-1（无法使用即：本次计算字符串长度的起始位begin，到该重复位之间字符第一个b，如：abcdbe，遇到第二个b时，需要清空ab）
4. 将b的标志位置为4（此次出现的位置），将begin指针指向位置1
5. 每次遇到重复字符时，首先记录当前长度，遍历结束后取最大

Discuss:

int lengthOfLongestSubstring(string s) {
        vector<int> dict(256, -1);
        int maxLen = 0, start = -1;
        for (int i = 0; i != s.length(); i++) {
            if (dict[s[i]] > start)//当前字符“曾经”是否出现在此子串中？
                start = dict[s[i]];//“曾经”出现那次作为新起点
            dict[s[i]] = i;//标志该字符出现的位置
            maxLen = max(maxLen, i - start);
        }
        return maxLen;
    }

思路差不多，在遇到相同字符时，处理方法更加简单，无需置空重复字符之前的无用字符，通过下标是否大于start（同begin）即可判断。
先判断dict[s[i]] > start