RGB Substring (hard version)

  1/**
  2 *    author: Akvicor
  3 *    created: 2019-07-25 00-14-18
  4**/
  5
  6#include <bits/stdc++.h>
  7
  8using namespace std;
  9
 10#ifdef DEBUG
 11#define FAST_IO 17
 12#else
 13#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
 14#define endl '\n'
 15#endif
 16
 17#define rep(i, n) for(int i = 0; i < (n); ++i)
 18#define reep(i, n) for(int i = 0; i <= (n); ++i)
 19#define lop(i, a, n) for(int i = a; i < (n); ++i)
 20#define loop(i, a, n) for(int i = a; i <= (n); ++i)
 21#define per(i, a, n) for(int i = a; i >= (n); --i)
 22#define peer(i, a, n) for(int i = a; i > (n); --i)
 23#define prec(x) fixed << setprecision(x)
 24#define ms(s, n) memset(s, n, sizeof(s))
 25#define all(v) (v).begin(), (v).end()
 26#define sz(x) ((int)(x).size())
 27#define mp(x, y) make_pair(x, y)
 28#define pb(x) push_back(x)
 29#define fi first
 30#define se second
 31#define MOD(x) const int MOD = (int)x
 32#define MAXN(x) const int MAXN = (int)x + 10
 33
 34typedef long long LL;
 35typedef unsigned long long ULL;
 36typedef pair<int, int> PII;
 37typedef vector<int> VI;
 38typedef vector<PII> VII;
 39
 40namespace SOL{
 41
 42const double EPS = 1e-6;
 43const double PI = acos(-1.0);
 44const int INF = 0x3f3f3f3f;
 45const LL LINF = 0x7f7f7f7f7f7f7f7f;
 46
 47/**  >------- Akvicor's Solution -------< **/
 48
 49MOD(1e9+7);
 50MAXN(1e6);
 51
 52int q, n, k;
 53int ans;
 54
 55void Find(string t, string &s){
 56	int l = 0, r = 0, res = 0;
 57	while(l <= n){
 58		while(r <= n && r-l < k){
 59			res += (s[r]==t[r%3]); // 记录有多少位匹配
 60			++r;
 61		}
 62		if(r-l < k) break;
 63		ans = max(ans, res);
 64		res -= (s[l]==t[l%3]); // 开头右移一位
 65		++l;
 66	}
 67}
 68
 69void solve(){
 70    FAST_IO;
 71    
 72    cin >> q;
 73	while(q-- > 0){
 74		ans = 0;
 75		string s;
 76		cin >> n >> k >> s;
 77		Find("RGB", s);
 78		Find("GBR", s);
 79		Find("BRG", s);
 80		cout << (k-ans) << endl;
 81	}
 82    
 83}
 84
 85/**  >----------------------------------< **/
 86
 87}
 88
 89int main(){
 90
 91#ifdef DEBUG
 92    int DEBUGCNT = 0;
 93    clock_t DEBUGstart, DEBUGfinish;
 94    double DEBUGduration;
 95    cout << endl << ">------- Akvicor's Solution -------<" << endl << endl;
 96    while (DEBUGCNT < 70) {
 97        cout << ">---> Test: #" << DEBUGCNT << " <---<" << endl;
 98        DEBUGstart = clock();
 99#endif
100
101        SOL::solve();
102
103#ifdef DEBUG
104        DEBUGfinish = clock();
105        DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
106        cout << ">---> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <---<" << endl << endl;
107        if (cin.eof()) break;
108        if (!cin.good()) break;
109        if (cin.fail()) break;
110        if (cin.bad()) break;
111        ++DEBUGCNT;
112    }
113    cout << ">----------------------------------<" << endl << endl;
114#endif
115
116    return 0;
117}