题目描述
给定一个字符串，找到最长的包含最多k个不同字符的子串，输出最长子串的长度即可。
Example：
给出字符串”eceba”，k = 2
输出答案3，最长包含最多2个不同字符的子串为”ece”。
官方题解（并没有看懂）：
最暴力的做法是穷举所有可能的子串，一共有n^2级别个不同的子串，然后对于每一个子串统计有多少不同的字符，如果少于k个就更新答案。这是一个三重循环的穷举，复杂度是O(n^3)。聪明的读者肯定想到了第二重和第三重循环可以合并，因为之前的统计信息可以继续使用而不需要每一次重新统计。这样的话穷举子串的开始位置和结束位置，复杂度是O(n^2)。如果在面试时提出了这个算法，面试官首先会表示认同，然后希望你进行优化。我们来看看如何进行优化。
在统计的过程中我们可以发现，当穷举的开始位置改变时我们会选择重新统计，但其实当开始位置改变时，我们之前记录的大部分信息都是有用的，我们只需在原有的统计结果上稍作修改。我们在两层for循环的时候其实会发现我们内层的fo循环其实并不需要每次都再重复遍历。比如外层for循环指针i每次向前移动变成i+1的时候，内层for循环的j没必要每次都退回到i的位置，其实是可以保留在j的位置不变的。因为可以证明对于从i+1到j-1这些情况都不会出现重复的元素，所以我们只用考虑从i+1到j就可以了。
自己的代码：
/**
*Author: xiaoran
*Solution:
*
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<fstream>
#define LL long long
using namespace std;
const int MAXN=1000005;
int test1_algorithm(char *s,int k){//O(n^3)
int len,m;
len = strlen(s);
m = 0;
for(int i=0;i<len;i++){
for(int j=i;j<len;j++){
int p=0,a[26]={0};
for(int t=i;t<=j;t++){
a[s[t]-'a']++;
}
for(int t=0;t<26;t++){
if(a[t]) p++;
}
if(p<=k) m=max(m,j-i+1);//因为是从大区间到小区间的遍历，第一次满足的子串就是结果
}
}
return m;
}
int test2_algorithm(char *s,int k){//记录上次的信息
int len,m,j,i;
len = strlen(s);
m = 0;
for(i=0;i<len;i++){
int p=0,a[26]={0};
for(j=i;j<len;j++){
a[s[j]-'a']=1;
p=0;
for(int t=0;t<26;t++){
if(a[t]) p++;
}
if(p<=k){
m = max(m,j-i+1);//去掉最后一个
}
}
}
return m;
}
int test3_algorithm(char *s,int k){//O(n)
int a[26]={0};
int m=0,len=strlen(s);
int start,end;
start=end=0;
while(end<len){
a[s[end++]-'a']++;
int p=0;
for(int i=0;i<26;i++){
if(a[i]) p++;
}
if(p<=k){
m = max(m,end-start);
}
if(p>k) a[s[start++]-'a']--;
}
return m;
}
int main()
{
//freopen("E:/","r",stdin);
//freopen("E:/","w",stdout);
char s[]="aabcdefgggg";
int k=3;
cout<<test1_algorithm(s,k)<<endl;
cout<<test2_algorithm(s,k)<<endl;
cout<<test3_algorithm(s,k)<<endl;
return 0;
}