LeetCode 3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Given “pwwkew”, 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.
解析：
给定一串字符，返回不重复子串的最大长度。比如给定字符”abcabcbb”，不重复最大子串是”abc”，长度为3.
暴力搜索法，直接挨个遍历判断，肯定会超时，需要进行改良。
方案1:
设置一个index标志位，记录当前最大子串的开始位置，用i记录当前遍历的位置，遍历当前元素与index之间的所有元素，如果存在重复，则将子串开始位置设置为重复元素的下一位，如果不重复，计算当前的最大长度，并与原有子串长度进行大小判断。整体复杂度为\(O(n^2)\)具体代码如下：
[cc lang=”C++”]
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.length();
if(len<=1)
return len;
int index =0;//子串的起始位置
int max_len = 1;//子串的最大长度
for(int i=1; i=index; j–)//将当前字符与index之间的所有字符进行判断
{
if(s[i]==s[j])//存在重复元素
{
index = j+1;//重置子串的起始位置
break;
}else{
if(max_len < i-j+1)//比较获取当前长度的最大值
max_len = i-j+1;
}
}
}
return max_len;
}
};
[/cc]
方案2:
采用空间换时间的方式，建立一个256位大小的哈希表，存放每个元素已经对应的下标，这样做的原因是ASCII表共能表示256个字符，所以可以记录所有字符。将所有字符的下标初始化为-1，并设置子串的起始位置start，如果当前字符对应哈希表中的数值大于start说明当前字符哈希表中已经存在，出现了重复元素，则更新哈希表中下标数值，更新子串起始位置，整个处理遍历一边即可，时间复杂度为\(o(n)\)

[cc lang=”C++”]
int lengthOfLongestSubstring(string s) {
vector dict(256, -1);//创建哈希表，初始每个元素对应的下标均为-1
int maxLen = 0, start = -1;//start标示子串的起始位置
for (int i = 0; i != s.length(); i++) {
if (dict[s[i]] > start)//存在重复元素
start = dict[s[i]];//重置start
dict[s[i]] = i;//更新哈希表数值
maxLen = max(maxLen, i – start);//计算最大长度
}
return maxLen;
}
[/cc]
参考：
https://www.cnblogs.com/grandyang/p/4480780.html
http://blog.csdn.net/suool/article/details/38360653

update in 2020.6.11

方案3：

双指针法，因为这里是要求一个满足条件的子串，可以考虑使用两个指针，然后采用滑动窗口的方式进行处理。具体分析如下，分析来自：https://www.cnblogs.com/grandyang/p/4480780.html

维护了一个滑动窗口，窗口内的都是没有重复的字符，需要尽可能的扩大窗口的大小。由于窗口在不停向右滑动，所以只关心每个字符最后出现的位置，并建立映射。窗口的右边界就是当前遍历到的字符的位置，为了求出窗口的大小，需要一个变量 left 来指向滑动窗口的左边界，这样，如果当前遍历到的字符从未出现过，那么直接扩大右边界，如果之前出现过，那么就分两种情况，在或不在滑动窗口内，如果不在滑动窗口内，那么就没事，当前字符可以加进来，如果在的话，就需要先在滑动窗口内去掉这个已经出现过的字符了，去掉的方法并不需要将左边界 left 一位一位向右遍历查找，由于 HashMap 已经保存了该重复字符最后出现的位置，所以直接移动 left 指针就可以了。维护一个结果 res，每次用出现过的窗口大小来更新结果 res，就可以得到最终结果啦。

这里可以建立一个 HashMap，建立每个字符和其最后出现位置之间的映射，然后需要定义两个变量 res 和 left，其中 res 用来记录最长无重复子串的长度，left 指向该无重复子串左边的起始位置的前一个，由于是前一个，所以初始化就是 -1，然后遍历整个字符串，对于每一个遍历到的字符，如果该字符已经在 HashMap 中存在了，并且如果其映射值大于 left 的话，那么更新 left 为当前映射值。然后映射值更新为当前坐标i，这样保证了 left 始终为当前边界的前一个位置，然后计算窗口长度的时候，直接用 i-left 即可，用来更新结果 res。

这里解释下程序中那个 if 条件语句中的两个条件 m.count(s[i]) && m[s[i]] > left，因为一旦当前字符 s[i] 在 HashMap 已经存在映射，说明当前的字符已经出现过了，而若 m[s[i]] > left 成立，说明之前出现过的字符在窗口内，那么如果要加上当前这个重复的字符，就要移除之前的那个，所以让 left 赋值为 m[s[i]]，由于 left 是窗口左边界的前一个位置（这也是 left 初始化为 -1 的原因，因为窗口左边界是从0开始遍历的），所以相当于已经移除出滑动窗口了。举一个最简单的例子 “aa”，当 i=0 时，建立了 a->0 的映射，并且此时结果 res 更新为1，那么当 i=1 的时候，发现a在 HashMap 中，并且映射值0大于 left 的 -1，所以此时 left 更新为0，映射对更新为 a->1，那么此时 i-left 还为1，不用更新结果 res，那么最终结果 res 还为1，正确，代码如下

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int result = 0;
        int left = -1;
        int len =  s.size();
        map<int, int> dict;
        for(int i =0; i < len; i++)
        {
            if(dict.count(s[i]) && dict[s[i]] > left)
            {
                left = dict[s[i]];
            }
            dict[s[i]] = i;
            result = max(result, i - left);
        }
        return result;
    }
};