D2. RGB Substring (hard version) codeforces round #575

链接：https://codeforces.com/contest/1196/problem/D2

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
string creatR(int n)
{
	string temp = "RGB";
	while (temp.size() < n)
	{
		temp += "RGB";
	}
	return temp;
}
string creatG(int n)
{
	string temp = "GBR";
	while (temp.size() < n)
	{
		temp += "GBR";
	}
	return temp;
}
string creatB(int n)
{
	string temp = "BRG";
	while (temp.size() < n)
	{
		temp += "BRG";
	}
	return temp;
}  //建立三个对比串
const int maxn = 2e5+10;
int a[maxn]; //相同为0，不同为1
int b[maxn]; //前缀和数组
int main()
{
	ios;
	int t;
	cin >> t;
	while (t--)
	{
		int n, k;
		cin >> n >> k;
		string s;
		cin >> s;
		int minn=inf;
		for (int i = 1; i <= 3; i++)
		{
			string temp;
			if (i == 1) temp = creatR(n);
			else if (i == 2) temp = creatG(n);
			else  temp = creatB(n);
			for (int j = 0; j < n; j++)
			{
				if (s[j] != temp[j]) a[j] = 1;
				else a[j] = 0;
				if (j >= 1) b[j] = a[j] + b[j - 1];
				else b[j] = a[j];
			}
			for (int h = k-1; h < n; h++)  //从第k个开始逐个向右计算
			{
				if (h - k >= 0)
					minn = min(minn, b[h] - b[h - k]);
				else
					minn = min(minn, b[h]);
			}
		}
		cout << minn << endl;
	}
}