人人公司2017校园招聘在线考试-编程二

题目-最长子串

描述

小M得到了一个由小写英文字符构成的字符串,她想从中挑选出一个美丽的子串。
一个字符串的子串是由其一段区间的字符所构成的字符串。
小M不喜欢重复,
所以她认为一个字符串是美丽的当且仅当它至多只包含Ca个字符’a’,Cb个字符’b’,…,Cz个字符’z’。
请你帮她找出一个最长的美丽的子串。

输入

第一行包含一个字符串s。1≤s的长度≤10^5
第二行包含26个整数表示0≤Ca,Cb……Cz≤10^9

输出

输出最长的美丽子串的长度。

Example

Input

aabaacaa
10 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Output

5

题解

思路

  • 遍历字符串,统计每个字符出现的个数,类似于滑动窗口
  • 如果符合,就继续扩大右端
  • 若不符合,就缩小左端
  • 更新最大长度
  • 时间复杂度 O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>

using namespace std;

char str[100005],n;
int c[26],cnt[100005][26];

int main()
{
while(scanf("%s",str)!=EOF)
{
for(int i=0;i<26;++i)
cin>>c[i];
int temp[26];
memset(temp,0,sizeof temp);
int maxlen=0;
for(int i=0,j=0;str[j];++j)
{
++temp[str[j]-'a'];
if(temp[str[j]-'a']>c[str[j]-'a'])
for(;i<=j;++i)
{
--temp[str[i]-'a'];
if(str[j]==str[i])break;
}
maxlen=max(maxlen,j-i+1);
}
cout<<maxlen<<endl;
}
}