关于最长不重复子串的问题

题目描述：Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

参考了很多人的blog，把看懂的汇集成自己的东西。参考博文

1.暴力+hash

首先是O(n2)的解法，大概思路是：遍历字符串，然后找出所有的子串，剔除掉中间有重复的字符的子串。例如当i=0时，那么就是找出包含s[i]在内的所有子串，剔除重复子串之后，就统计出一个最大的长度值，由于是最大连续子串，若发现该子串有重复的话，直接跳出内层循环。去重复可以考虑hash，长度也就是j-i。

还记得这是我去美团网的一道面试题，当时很菜，hash没想到，就简单的两层循环来统计最大长度，后来面试官直接给个例子abbcbefa，这样若i=0时只考虑a是否重复，直接得出答案就是7啦，而里面包含了三个b，没有考虑到子串中除i角标以外的角标对应的值是否有重复。

这里的hash大概的思路就是：以abcbef这个串为例，用一个数组visit记录每个元素曾出现的下标，初始化为0。i=0，从s[0]开始，令visit['a']=1，然后j=i+1依次考察之后的每个字符，如visit['b'] == 0,然后visit['b'] = 1，直到s[3]，visit['b'] != 0，说明'b'在前面已经出现过了，此时可得到一个不重复串"abc"，刷新当前的最大长度，然后更新pos['b']及起始串位置。

借鉴~过程如下：
1、建一个256个单元的数组，每一个单元代表一个字符，数组中保存上次该字符出现的位置；
2、依次读入字符串，同时维护数组的值；
3、如果遇到冲突了，考察当前起始串位置到冲突字符的长度，如果大于当前最大长度，则更新当前最大长度并维护冲突字符的位置，更新起始串位置，继续第二步。

 1 #include<iostream>
 2 #include<string>
 3 #include<cstring>
 4 using namespace std;
 5 int visit[256];
 6 void solve6(string s)
 7 {
 8     int maxlen=-1;
 9     int i,j;
10     for (i=0;i<s.size();++i)
11     {
12         memset(visit,0,sizeof(visit));
13         visit[s[i]]=1;
14         for (j=i+1;j<s.size();++j)
15         {
16             if (visit[s[j]]==0)
17                 visit[s[j]]=1;
18             else 
19             {
20                 if((j-i)>maxlen)
21                     maxlen=j-i;
22                 break;
23             }
24 
25         }
26         if(j==s.size()&&(j-i)>maxlen)
27             maxlen=j-i;
28         
29 
30     }
31     cout<<maxlen<<endl;
32 }
33 int main() 
34 {
35     string s;
36     while (cin>>s)
37     {
38         solve6(s);
39         s.clear();
40     }
41     return 0;
42 }

2.自己写的hash改进版（加上位置记录）

struct myarray{
        bool flag;
        int loc;
    };

　　其实只需要一层for循环就能搞定，从头开始遍历，一边更新dps中出现过没有出现过的字符，若发现相同字符，先记录下本次遍历的长度(和最小长度比较)，然后找到该字符第一次出现的位置，从该位置之后的一个位置再开始遍历，总结下就是:有相同就回溯。

　　一开始想错了，认为只要遇到相同的字符，就把该字符之前的长度记录，然后下一次就直接从该字符的下一个字符继续遍历，错在忽略了两个相同字符之间的长度。

　　例如adfghqjdex，分析如下图:

代码：

#include <string>
#include <iostream>
using namespace std;
class Solution {
private:
    struct myarray{
        bool flag;
        int loc;
    };
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty())
            return 0;
        struct myarray dps[1000];
        for (int i=0; i<1000; ++i) {
            dps[i].flag=false;
            dps[i].loc=-1;
        }
        int reslen=0;
        int nextStart=0;
        int i;
        for(i=0;i<s.size();++i)
        {
            if(dps[s[i]].flag==false)
            {
                dps[s[i]].flag=true;
                dps[s[i]].loc=i;
            }
            else
            {
                if(i-nextStart>reslen)
                    reslen=i-nextStart;
                nextStart=dps[s[i]].loc+1;
                i=nextStart-1;
                for (int i=0; i<1000; ++i)
                {
                    dps[i].flag=false;
                    dps[i].loc=-1;
                }
            }
        }
        if(i==s.size()){
            if(s.size()-nextStart>reslen)
                reslen=s.size()-nextStart;
        }
        return reslen;
    }
};
int main()
{
    Solution so;
    cout<<so.lengthOfLongestSubstring("wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco")<<endl;
}