← 返回题目列表

Codeforces · 1196/D2

D2. RGB 子串(硬版)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是输入的大小。

给定一个字符串 $$$s$$$,由 $$$n$$$ 个字符组成,每个字符是“R”、“G”或“B”。

您还获得了一个整数 $$$k$$$。您的任务是更改初始字符串 $$$s$$$ 中的最小字符数,以便更改后将出现一个长度为 $$$k$$$ 的字符串,该字符串是 $$$s$$$ 的子字符串,也是无限字符串“RGBRGBRGB ...”的子字符串。

如果存在正整数 $$$i$$$,使得 $$$a_1 = b_i$$$、$$$a_2 = b_{i + 1}$$$、$$$a_3 = b_{i + 2}$$$、...、$$$a_{|a|} = b_{i,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串+ |一个| - 1}$$$。例如,字符串“GBRG”、“B”、“BR”是无限字符串“RGBRGBRGB ...”的子字符串,而“GR”、“RGR”和“GGG”则不是。

您必须回答 $$$q$$$ 独立查询。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。然后是 $$$q$$$ 查询。

查询的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) - 字符串 $$$s$$$ 的长度和子字符串的长度。

查询的第二行包含一个字符串 $$$s$$$,由 $$$n$$$ 字符“R”、“G”和“B”组成。

保证所有查询的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。

输出

对于每个查询,打印一个整数 - 您需要在初始字符串 $$$s$$$ 中更改的最小字符数,以便更改后 $$$s$$$ 中将有一个长度为 $$$k$$$ 的子字符串,它也是无限字符串“RGBRGBRGB ...”的子字符串。

示例

输入 #1

3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR

输出 #1

1
0
3

注意

在第一个示例中,您可以将第一个字符更改为“R”并获得子字符串“RG”,或者将第二个字符更改为“R”并获得“BR”,或者将第三个、第四个或第五个字符更改为“B”并获得“GB”。

在第二个示例中,子字符串是“BRG”。