某天你得到了一个长度为n(1<=n<=500000)的字符串，并且这个字符串只包含小写字母。现在允许你修改m(1<=m<=n)个位置的字母，修改完毕你要选取这个字符串的一个连续子串，如果这个子串只包含一种字母，那么这个连续子串是一个完美字符串。你希望得到的完美字符串长度尽可能长，请计算出你所能得到的最长长度是多少。
样例输入
- 8 1
- aabaabaa
样例输出
- 5（把任意一个b换成a，得到的最长完美字符串为aaaaa）
样例输入
- 8 2
- aabaabaa
样例输出
- 8 （把两个b都换成a，得到最长完美子串为aaaaaaaa）
思路
- 这个题要求的是最后能得到的最长的完美子串的长度是多少，这个完美子串是由同一个字符构成的。那么可以枚举下最后最长的这个完美子串是由哪个字母组成的。
- 那么问题就转换成了如何求只包含某一个字符的最长的完美串。解决这个问题之后可以遍历26个字母中的每一个，然后就能得到最终的答案了。
全部评论
(1) 回帖