C. 【普及】最长的平衡子串3

    传统题 100ms 32MiB

【普及】最长的平衡子串3

题目背景

  • 1、请大家注意数据范围:
  • 2、前面 7272 分是大家熟悉的问题(k=0k=0)
    • 2-1、k=0k=0 也就是说出现次数 相同
  • 3、然后 2828 分只需要稍作修改(k=1k=1)
    • 3-1、特殊性质:字符串只包含 'a','b',不包含 'c'
    • 3-2、看看答案有什么规律,想想查询时如何修改保存的状态?

题目描述

给你一个只包含字符 'a','b' 和 'c' 的字符串 ss。

如果一个 子串 中所有 不同 字符出现的次数 相差不超过 kk,则称该子串为 平衡 子串。

请输出 ss 的 最长平衡子串 的 长度 。

子串 是字符串中 连续的、非空 的字符序列。

输入格式

第一行包含 11 个整数 TT,表示数据组数

每组数据的第 11 行包含 22 个整数 n,kn, k 每组数据的第 22 行包含一个长度为 nn 字符串 ss

保证同一组内所有字符串的长度之和不超过 2×1052 \times 10^5

输出格式

对于每组数据输出 11 行包含 11 个数,表示 最长平衡子串 的 长度

4
5 0
abbac
5 0
aabcc
3 0
aba
5 0
aaabb
4
3
2
4
3
5 1
aaabb
5 1
aabba
6 1
aabbaa
5
5
5

提示

【样例 1 解释】

  • 这一组样例都满足 k=0k=0,也就是要满足所有 不同 字符出现的次数 相同
  • 样例 1:最长的平衡子串是 "abba",因为不同字符 'a' 和 'b' 都恰好出现了 22 次
  • 样例 2:最长的平衡子串是 "abc",因为不同字符 'a'、'b' 和 'c' 都恰好出现了 11 次
  • 样例 3:最长的平衡子串之一是 "ab",因为不同字符 'a' 和 'b' 都恰好出现了 11 次。另一个最长的平衡子串是 "ba"
  • 样例 4:最长的平衡子串是 "aaa",因为只包含 'a'

【样例 2 解释】

  • 这一组样例都满足 k=1k=1,也就是要满足所有 不同 字符出现的次数 相差不超过 11
  • 样例 1:最长的平衡子串是 "aaabb",因为不同字符 'a' 出现了 33 次,'b' 出现了 22 次,'a' 和 'b' 出现的次数相差不超过 11
  • 样例 2:最长的平衡子串是 "aabba"
  • 样例 3:最长的平衡子串是 "aabba" 或者 "abbaa"

【数据范围】

对于所有测试数据,均有:

  • 1≤T≤1041 \le T \le 10^{4}
  • 1≤n≤1051 \le n \le 10^{5}
  • 0≤k≤10 \le k \le 1
  • ss 仅包含字符 'a','b','c'
  • 保证同一组内的字符串长度之和不超过 2×1052 \times 10^5
测试点编号 n≤n \le kk 特殊性质 分值
1∼31 \sim 3 500500 00 无 1212
4∼84 \sim 8 10510^5 A 2020
9∼189 \sim 18 无 4040
19∼2519 \sim 25 11 A 2828
  • 特殊性质 A:ss 仅包含字符 'a','b',没有 'c'
请思考后再点击查看提示

来源