算法随笔2：无重复字符的最长子串

题目是这样的：

给定一个字符串s, 请找出其中不含有重复字符的最长子串的长度。

例如：s="abcabcbb",

答案：3。因为不含有重复字符的最长子串为"abc"。

我们可以这么考虑这个问题。最终的答案的起始字母必然是字符串s里的其中一个字母。这句话听起来像是一句废话。但有时往往一道算法题的解题思路，就是从最简单的事实入手的。

基于上面的事实，我们需要找到每个字母为首的子串，让这个子串不含有重复字符。上面的例子中有8个字符，那么我们需要找到8个子串。那么这8个子串中最长的那个子串，即为最终的答案。

我们这里使用一个双指针的策略(左指针，右指针)。左指针循环探测字符串s里的每一个字符。右指针负责探测，是否有重复字符。具体做法如下：

让左指针先指向字符串s的首字符a, 让这个字母做为候选答案的首字母，把它放入一个集合set中，然后右指针指向下一个字符next_letter，此时会出现两种情况：

1. 如果set中没有和next_lettter相同的字符，next_letter则放入set中。右指针向右移动一格

2. 如果set中有相同的字符，则不放入，此时子串的长度，就是以a为首的子串的长度。记录在一个变量len里，表示当前最长的子串的长度。同时把a从set中移除。左指针指向下一个字符b。因为右指针此时未动，所以继续判断set中是否有和next_lettter相同的字符。按同样的两种情况的方案处理。

直到右指针到达字符串的末尾。最终的len值就是最后的答案。这里有几点需要注意：

1. 当左指针和右指针重合时，需要右移右指针，来维持一个子串的判断。且set中需要放入左指针指向的字符。

2. 每找到一个子串的长度，需要和len做比较，把当前最大的值存入len。

3. 还有一些其它的算法细节，需要在实际编写代码时注意。在此就不展开说了。

此算法在最坏的情况下，左右指针各遍历整个字符串一次，所以算法的时间复杂度仍是O(N)。