Substring Importance  ZCO 2018

All submissions for this problem are available.
You are given a string of N characters, (S_{1}, S_{2}, S_{3}, ... , S_{N}), in which each character is 'X', 'Y' or 'Z'. A substring is a consecutive portion of the string. That is, a substring will be of the form (S_{i}, S_{i+1}, ... , S_{j}), for some i and j. A substring is said to be Good if it starts with an 'X', ends with a 'Z' and has a length which is a multiple of 3.
The Importance of a particular substring (S_{i}, S_{i+1}, ... , S_{j}), is the number of Good substrings that it intersects with. That is, it is the number of x and y, such that (S_{x}, S_{x+1}, ... , S_{y}) forms a Good substring, and there is some z such that i ≤ z ≤ j and x ≤ z ≤ y. This signifies that there is at least a single index z, which should be common.
Given an integer K, you need to find a substring of length exactly K which has the minimum Importance, and print the minimum Importance.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of each test case follows.
The first line of each test case contains two integers N and K denoting the number of characters in the input string and the length of the substring needed.
The second line of each test case contains N space separated characters denoting the input string.
Output
For each test case, output a single line containing a single integer, which should be the minimum Importance of a K length substring.
Constraints
 1 ≤ T ≤ 10
 1 ≤ K ≤ N ≤ 10^{5}
Subtasks:
 Subtask #1 (10 points): 1 ≤ K ≤ N ≤ 100
 Subtask #2 (15 points): 1 ≤ K ≤ N ≤ 1000
 Subtask #3 (35 points): K = 1
 Subtask #4 (40 points): Original constraints.
Example
Input: 2 9 3 X Y Z Z Y X X Y Z 4 2 Y X Y Z Output: 1 1
Explanation
Test case 1:The input string is (X, Y, Z, Z, Y, X, X, Y, Z). There are totally 3 Good substrings, which are underlined:
 (X, Y, Z, Z, Y, X, X, Y, Z)
 (X, Y, Z, Z, Y, X, X, Y, Z)
 (X, Y, Z, Z, Y, X, X, Y, Z)
We now need to find a substring of length 3 which intersects with the minimum number of Good substrings. In this example, there is an unique such substring: (X, Y, Z, Z, Y, X, X, Y, Z). Its Importance is 1 because it intersects with only the third Good substring. We cannot do better. Hence the answer is 1.
Test case 2:The input string is (Y, X, Y, Z). There is only one Good substring: (Y, X, Y, Z). But every substring of length 2 intersects with this Good substring, and hence the Importance of every substring of length 2 is 1. Therefore the minimum is also 1, and that is the answer.
Author:  admin3 
Date Added:  10112017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions