Codeforces 7-24 div3 RGB Substring（hard version）_rgb substring (hard version)

RGB Substring (hard version)

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
The only difference between easy and hard versions is the size of the input.

problem

You are given a string s consisting of n characters, each character is ‘R’, ‘G’ or ‘B’.

You are also given an integer k. Your task is to change the minimum number of characters in the initial string s so that after the changes there will be a string of length k that is a substring of s, and is also a substring of the infinite string “RGBRGBRGB …”.

A string a is a substring of string b if there exists a positive integer i such that a1=bi, a2=bi+1, a3=bi+2, …, a|a|=bi+|a|−1. For example, strings “GBRG”, “B”, “BR” are substrings of the infinite string “RGBRGBRGB …” while “GR”, “RGR” and “GGG” are not.

You have to answer q independent queries.

Input

The first line of the input contains one integer q (1≤q≤2⋅105) — the number of queries. Then q queries follow.

The first line of the query contains two integers n and k (1≤k≤n≤2⋅105) — the length of the string s and the length of the substring.

The second line of the query contains a string s consisting of n characters ‘R’, ‘G’ and ‘B’.

It is guaranteed that the sum of n over all queries does not exceed 2⋅105 (∑n≤2⋅105).

Output

For each query print one integer — the minimum number of characters you need to change in the initial string s so that after changing there will be a substring of length k in s that is also a substring of the infinite string “RGBRGBRGB …”.

Example

input

3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR

output

1
0
3

Note

In the first example, you can change the first character to ‘R’ and obtain the substring “RG”, or change the second character to ‘R’ and obtain “BR”, or change the third, fourth or fifth character to ‘B’ and obtain “GB”.

In the second example, the substring is “BRG”.

题意

您将得到一个由n个字符组成的字符串s，每个字符都是“r”、“g”或“b”。

还为您提供了一个整数k。您的任务是更改初始字符串s中的最小字符数，以便更改后将有一个长度为k的字符串，该字符串是s的子字符串，也是无限字符串“rgbrgbrgbb…”的子字符串。

如果存在正整数i（a1=bi，a2=bi+1，a3=bi+2，…，a a=bi+a−1），则字符串a是字符串b的子字符串。例如，字符串“gbrg”、“b”、“br”是无限字符串“rgbrgbrgb…”的子字符串，而“gr”、“rgr”和“ggg”则不是。

分析

对于这个 hard 版本的 Substring ，比起简易版本的Substring，实际上控制了时间复杂度，要是按照之前的方法，就会 Time Limitted ；所以，我们要在原先代码的基础上进行优化，在上一篇简易版
https://blog.csdn.net/weixin_42664622/article/details/97242264
中，我们对原字符串从 0 遍历到 s.size() - k + 1，每一次找到长度为K的子字符串，并找出那个改动最小的即是答案。但是，这样计算的复杂度是（s.size() - k + 1）＊ｋ，其实，我们遍历的数据是可以叠加使用的，例如我们遍历的１到ｋ的数据在２到k+１时，只需要减去第１个数据加上第k+１个数据就可以了，根据这个方法，我们可以写出如下代码。

代码

 #include<bits/stdc++.h>
using namespace std;
 
const int MAX_N=2e5+100;
const char c[3][3]={{'R','G','B'},{'G','B','R'},{'B','R','G'}};
 
int q,n,k;
string s;
 
int main(){  
	cin>>q;
	while(q--){
		cin>>n>>k>>s;
		int sum[3]={0,0,0};
		int ans=MAX_N;

		for(int i=0;i<s.size();i++){
			for(int j=0;j<3;j++){  // 三种不同的循环 “rgb” 、“gbr”、“brg
				if(c[j][i%3]!=s[i]) 
					sum[j]++;			 //对于每一个i，如果不相同，就给最终的值加1
					if(i>=k-1){
						if(i>=k)
							if(c[j][(i-k)%3]!=s[i-k]) sum[j]--;	//对一个新的 k 子串，去掉原来子串中的第一个
						ans=min(sum[j],ans);  // 找到改动最小的
				}
			}
		} 
		cout<<ans<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31