人人公司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];

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;
    }
}