对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。
穷举肯定是不行的，这个问题要用到类似于动态规划的算法：
已知字符串A，设定数组len，另len[i]表示以元素A[i]结尾的，最长的无重复子串。只要求出来len数组中的最大值，即为问题的解。
目前的问题是，已知len[i-1],如何求len[i]?
我们当前处理A[i],已知len[i-1]==5,就可以知道以A[i-1]做结尾的最大无重复子串的长度是5，就可以找到该子串的起始位置p.
- 因为A[i]=='C',如果发现从A[p..i-1]内没有出现‘C’,就可以把新成员C纳入到该子串中。所以以A[i]为结尾的最大无重复子串是A[p..i].
-
如果发现从A[p..i-1]内出现‘C’,那么以A[i]为结尾的最大无重复子串，只能是A[q+1..i].
为了提高搜索某字符在字符串中上一次出现的位置，我们使用一个哈希表来存储。该表初始化所有元素为-1，提高通用性。
int longestSubstring(string A, int n) {
//哈希表：每个元素上次出现的位置
int pos[256];
for(int i=0;i<256;++i)
pos[i]=-1;//初始-1可以统一化使用
//以i为结尾的最大无重复串长度
int *len=new int[n]();
//初始化0号字符的情况
len[0]=1;
pos[A[0]]=0;
for(int i=1;i<n;++i){
//为了处理方便，q的定义与图示
int q=pos[A[i]]+1;
int p=i-len[i-1];
len[i]=q<p?i-p+1:i-q+1;
pos[A[i]]=i;
}
//找出len数组中最大值
int max=0;
for(int i=0;i<n;++i){
if(len[i]>max)
max=len[i];
}
delete[] len;
return max;
}
