今日头条2018校园招聘后端方向-附加编程题

发表于 | 分类于 ，

题目

描述

有一个字符串,只包含 26 个小写字母,相邻两个字母可以交换,
给定一个字符串 str 及交换次数 m,
试问在交换次数不超 m 的情况下,连续相同的字符长度最大是多少

输入

1 行,一个字符串 str 及交换次数 m

输出

最大连续相同的字符长度

Example

Input

abacaa 3

Output

3

题解

思路

  • 作者：桐ヶ谷和人
  • 原文: 今日头条2018校招编程题思路
  • 枚举每种字母，计算该字母在字符串中出现的位置。
  • 再枚举以该字符每个位置为中心点，两边的字符往这个中心靠拢，计算一个距离的前缀和， 再枚举左端点，二分找右端点。
  • 复杂度O(26*|s|*|s|*log(|s|))