首页 > 试题广场 >

eli和字符串

[编程题]eli和字符串

热度指数：98 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

eli拿到了一个仅由小写字母组成的字符串。
她想截取一段连续子串，这个子串包含至少 $k\$ 个相同的某个字母。
她想知道，子串的长度最小值是多少？
注：所谓连续子串，指字符串删除头部和尾部的部分字符（也可以不删除）剩下的字符串。例如：对于字符串 $\mathit{“arcaea”}$ 而言， $\mathit{“arc”}$ 、 $\mathit“rcae”$ 都是其子串。而 $\mathit“car”$ 、 $\mathit“aa”$ 则不是它的子串。

输入描述:

第一行输入两个正整数  和  
输入仅有一行，为一个长度为  的、仅由小写字母组成的字符串。

输出描述:

如果无论怎么取都无法满足条件，输出  。
否则输出一个正整数，为满足条件的子串长度最小值。

示例1

输入

5 2
abeba

输出

说明

选择子串，长度为3，其中包含相同的两个'b'

备注:

算法知识视频讲解

--嘤色暴撃--

发表于 2020-02-04 18:30:10

简单的队列模拟首先把每一个字母加入队列，我们用head，tail表示队列的头和尾head是头的后一位，tail是尾那么目前所查找的区间长度为tail-head+1， tail=head+1时队列为空我们先不断地加入字母(按顺序)直到其中出现重复的k个字母，这时候就要把头缩回来(++head)，直到展开全文

__Aurora__

发表于 2020-02-04 19:18:38

本题其实用前缀和就可以做因为每个字母出现一次，那么它的出现次数就+1，所以记录它的每个出现位置，用数组trace记录具体做法：struct node{int trace[200010], index=1;} lt[26]; 【trace类似于vector，莫习惯这么写了，见谅】由于要求同个字母出现展开全文

longlongyu

发表于 2020-02-05 11:01:59

题目描述：eli拿到了一个仅由小写字母组成的字符串。她想截取一段连续子串，这个子串包含至少k个相同的某个字母。她想知道，子串的长度最小值是多少？注：所谓连续子串，指字符串删除头部和尾部的部分字符（也可以不删除）剩下的字符串。思路：利用for遍历26个字母，每个字母利用尺取法查找满足条件的最小长度。A 展开全文