NC222216. 音乐家的曲调
描述
疲惫的你闲暇之余最爱听牛少芬的《命运交响曲》，其曲调在你脑中甚至可以抽象成一个长度为且仅包含小写字母的字符串
。
一天，你最好的朋友得知你对《命运交响曲》颇有研究，想让你提供三段互不重复的《命运交响曲》片段，且要求这三段片段的优美度之和最大。你转头一想，也就是从《命运交响曲》曲调抽象成的这个字符串中选出三个不相交的区间，使这三个区间的区间长度之和最大。当然，要求选出的任意一个区间，区间内每种小写字母的出现次数不能超过。
请问最大的区间长度之和是多少?
输入描述
第一行两个正整数
,
，
,
。
第二行一个长度为
。
输出描述
输出最大区间长度之和。
示例1
输入:
8 1 abccbaaa
输出:
7
C++ 解法, 执行用时: 167ms, 内存消耗: 127608K, 提交时间: 2021-06-25 19:24:01
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e7+10;
int n,m,f[3][N],v[26];
char s[N];
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",s+1);int z=1;
for(int i=1;i<=n;i++){
int x=s[i]-'a';v[x]++;
while(v[x]>m)v[s[z]-'a']--,z++;
f[2][i]=max(f[1][z-1]+(i-z+1),f[2][i-1]);
f[1][i]=max(f[0][z-1]+(i-z+1),f[1][i-1]);
f[0][i]=max(i-z+1,f[0][i-1]);
}
printf("%d\n",f[2][n]);
}