题目背景

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

题目描述

给你一个只包含字符 'a'，'b' 和 'c' 的字符串 $s$。

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

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

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

输入格式

第一行包含 $1$ 个整数 $T$，表示数据组数

每组数据的第 $1$ 行包含 $2$ 个整数 $n, k$ 每组数据的第 $2$ 行包含一个长度为 $n$ 字符串 $s$

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

输出格式

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

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=0$，也就是要满足所有 不同 字符出现的次数 相同
• 样例 1：最长的平衡子串是 "abba"，因为不同字符 'a' 和 'b' 都恰好出现了 $2$ 次
• 样例 2：最长的平衡子串是 "abc"，因为不同字符 'a'、'b' 和 'c' 都恰好出现了 $1$ 次
• 样例 3：最长的平衡子串之一是 "ab"，因为不同字符 'a' 和 'b' 都恰好出现了 $1$ 次。另一个最长的平衡子串是 "ba"
• 样例 4：最长的平衡子串是 "aaa"，因为只包含 'a'

【样例 2 解释】

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

【数据范围】

对于所有测试数据，均有：

• $1 \le T \le 10^{4}$
• $1 \le n \le 10^{5}$
• $0 \le k \le 1$
• $s$ 仅包含字符 'a'，'b'，'c'
• 保证同一组内的字符串长度之和不超过 $2 \times 10^5$

• 特殊性质 A：$s$ 仅包含字符 'a'，'b'，没有 'c'

来源