D2. RGB Substring (hard version)

The only difference between easy and hard versions is the size of the input.

You are given a string ss consisting of nn characters, each character is 'R', 'G' or 'B'.

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

A string aa is a substring of string bb if there exists a positive integer ii such that a1=bia1=bi, a2=bi+1a2=bi+1, a3=bi+2a3=bi+2, ..., a|a|=bi+|a|−1a|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 qq independent queries.

Input

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

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

The second line of the query contains a string ss consisting of nn characters 'R', 'G' and 'B'.

It is guaranteed that the sum of nn over all queries does not exceed 2⋅1052⋅105 (∑n≤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 ss so that after changing there will be a substring of length kk in ss that is also a substring of the infinite string "RGBRGBRGB ...".

Example

input

Copy

3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR

output

Copy

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".

come from ：Problem - 1196D2 - Codeforces

translate ( Probably )：

You have a length of n String , Only three characters  R G B, Then you want to cut a length of k Modify some letters , Let it be of length k Of RGB Substring ,RGB The substring is RGBRGBRGB...., A segment intercepted from such an infinite loop string . We hope that the number of modifications will be as few as possible , Please return to this minimum number of modifications .

The input on the first line ：q , Represents the number of test cases , The scope is 1 To 2e5

The first line of each test case ： Two figures ,n and k,n Represents string length ,k Represents the intercept length ,k Less than or equal to n, Both ranges 1 To 2e5

The second line of each test case ： A string , Represents the string modified by the current bit , The scope and of all test cases will not exceed 2e5

Input ：

3

5 2

BGGGG

5 3

RBRGR

5 5

BBBRR

Output ：

1

0

3

explain ：

RGB One length of is 2 The substring of is BR, It and BG The difference is one character , So the first one is 1

RGB The length is 3 There are BRG, And substring BRG perfect match , So the second one is 2

RGB The length is 5 There are RGBRG, and BBBRR Difference between 3 individual , So the third one is 3

Method 1： The prefix and

1. Use dp Array records strings ending in a letter , The total number of modifications required

2. Subtract the number of modifications corresponding to the letter that begins with the backward push

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Reader r = new Reader();
        //3
        //5 2
        //BGGGG
        //5 3
        //RBRGR
        //5 5
        //BBBRR
        int m = r.nextInt();
        for(int a = 0; a < m; a++){
            int n = r.nextInt();
            int k = r.nextInt();
            String s = r.nextLine();
            int[][] dp = new int[s.length()+1][3];//RGB
            for(int i = 0; i < s.length(); i++){
                char c = s.charAt(i);
                dp[i+1][0]= (c=='R'?0:1) +dp[i][2];
                dp[i+1][1]= (c=='G'?0:1) +dp[i][0];
                dp[i+1][2]= (c=='B'?0:1) +dp[i][1];
            }
 
            int move = 3-k%3;
            int ans = k;
            for(int i = k; i <= s.length(); i++){
                ans = Math.min(ans,dp[i][0]-dp[i-k][move%3]);
                ans = Math.min(ans,dp[i][1]-dp[i-k][(move+1)%3]);
                ans = Math.min(ans,dp[i][2]-dp[i-k][(move+2)%3]);
            }
            System.out.println(ans);
        }
    }
 
 
 
    static class Reader {
        private BufferedReader br;
        private StringTokenizer st;
 
        Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(br.readLine());
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextInt();
            return arr;
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }
    }
}

Time complexity ：O(n)

Spatial complexity ：O(n)【 Remove input 】

Method 2： The sliding window

  Post the code , Group friends said it was too troublesome , It's much simpler to use a sliding window . Thinking about 5 minute , Thought of the writing method of sliding window .

1. Three characters , There are only three possibilities to start , Then cycle 3 Try it every time

2. The specified window size is k, arrive k After , Each additional tail , Add up , Subtract a beginning , Subtract

3. The optimal solution of sliding process calculation

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Reader r = new Reader();
        //3
        //5 2
        //BGGGG
        //5 3
        //RBRGR
        //5 5
        //BBBRR
        int m = r.nextInt();
        char[] cs1 = new char[]{'R','G','B'};
        char[] cs2 = new char[]{'G','B','R'};
        char[] cs3 = new char[]{'B','R','G'};
        char[][] cs = new char[][]{cs1,cs2,cs3};
        for(int a = 0; a < m; a++){
            int n = r.nextInt();
            int k = r.nextInt();
            String s = r.nextLine();
            int ans = k;
            for(int i = 0; i < 3; i++){
                int cnt = 0;
                for(int j = 0; j < k; j++){
                    if(cs[i][j%3]!=s.charAt(j)) ++cnt;
                }
                ans = Math.min(cnt,ans);
                for(int j = k; j < n; j++){
                    if(cs[i][(j-k)%3]!=s.charAt(j-k)) --cnt;
                    if(cs[i][j%3]!=s.charAt(j)) ++cnt;
                    ans = Math.min(cnt,ans);
                }
            }
            System.out.println(ans);
        }
    }
 
 
 
    static class Reader {
        private BufferedReader br;
        private StringTokenizer st;
 
        Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(br.readLine());
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextInt();
            return arr;
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }
    }
}

Time complexity ：O(n)

Spatial complexity ：O(1)【 In addition to the input 】

Then I was confused , This writing method is so simple , Why is there no improvement in efficiency ？ The Spirit gave a hint ： check Java Read and write . In fact, fast reading is already in use , Write fast Not yet , Have a try , Sure enough, it's much faster . in addition , Find out There is no need to list it three times RGB Different ways of writing , Use i The index represents the offset That's all right. , With these two optimizations , Time efficiency is much better , as follows ：

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Reader r = new Reader();
        //3
        //5 2
        //BGGGG
        //5 3
        //RBRGR
        //5 5
        //BBBRR
        PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
        int m = r.nextInt();
        char[] cs1 = new char[]{'R','G','B'};
        for(int a = 0; a < m; a++){
            int n = r.nextInt();
            int k = r.nextInt();
            String s = r.nextLine();
            int ans = k;
            for(int i = 0; i < 3; i++){
                int cnt = 0;
                for(int j = 0; j < k; j++){
                    if(cs1[(j+i)%3]!=s.charAt(j)) ++cnt;
                }
                ans = Math.min(cnt,ans);
                for(int j = k; j < n; j++){
                    if(cs1[(i+j-k)%3]!=s.charAt(j-k)) --cnt;
                    if(cs1[(i+j)%3]!=s.charAt(j)) ++cnt;
                    ans = Math.min(cnt,ans);
                }
            }
 
            out.println(ans);
            out.flush();// Refresh after outputting once 
        }
    }
 
 
 
    static class Reader {
        private BufferedReader br;
        private StringTokenizer st;
 
        Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(br.readLine());
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextInt();
            return arr;
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }
    }
}

  Just when I think efficiency is good , The spirit God said ： Not ah , One of me go Just run 200 many Why are you so slow ？ hold flush Interview outside ：

  This code will not be posted , The same as before , The only difference is flush Put it outside . It's great , I learned a lot about tea today ！