THIS EDITORIAL IS AN UNOFFICIAL ONE AND THE REASONING BEHIND THE LOGIC MAY DIFFER FROM THE OFFICIAL ONE.
PROBLEM LINK:
DIFFICULTY:
Easy
PREREQUISITES:
Sliding Window Algorithm
PROBLEM:
The problem statement is clear and short. It can’t be more shorter.
QUICK EXPLANATION:
Calculate all the points from where a Good substring starts, and all the points where the Good substring ends. Now, run a window of length K through the whole array. This is done to minimize the time complexity from O(N * N) to only O(N), thus solving it for 100 points.
EXPLANATION:
Please go step by step, as the points are inter-related.
AC (10pts)
Let us first define a Brute Force approach to the problem.
So, we will keep an array which will help us in calculating the minimum Importance of a substring of length K.
Definition of arr(i)
arr[i] = the number of Good substrings the ith index overlaps with.
So what are we going to do will be increasing the length by 3 every time, and iterate through the whole array. We check the following,
- a[start_pos] == X
- a[end_pos] == Z.
If both are true, now we will update our arr[] array which will take O(len) time.
Solution Snippet
for(int len = 3; len <= n; len += 3) { //the length of the Good substring
for(int i = 1; i <= n - len; i++) { //1 indexing
int j = i + len;
if(a[i] == 'X' && a[j] == 'Z') //checking the conditions
{
for(int k = i; k <= j; k++) {
arr[k]++; //incrementing the value of arr[i], arr[i + 1] ... arr[j]
}
}
}
}
So we are increasing the length of the Good substring - O(N)
Within that, we are iterating through the array - O(N)
Within that we are updating our arr[] array - O(N)
So, The Time Complexity of this Approach is (O(N * N * N ) )
This will AC only on the first sub-task. 
This motivates us to make this code efficient.
AC (25pts)
In the brute force solution, when we are traversing for each i and j, and checking whether the condition holds true, can’t we update the values after the traversing is over? This will make this code quite efficient. But how?
Answer to this question
We can just easily store i and j in a vector of pairs. Then, we can traverse it after the loops end.
Solution Snippet
vector<pair<int, int> >pos; //The pair is start_pos, end_pos of each Good substring
for(int len = 3; len <= n; len += 3) { // The length of the Good substring
for(int i = 1; i <= n - len; i++) { // 1 indexing
int j = i + len;
if(a[i] == 'X' && a[j] == 'Z') { // checking the conditions
pos.push_back(make_pair(i, j)); //making the pair
}
}
}
for(int i = 0; i < pos.size(); i++) { // iterating through the pos array
for(int j = pos[i].first; j <= pos[i].second; j++) { // updating arr[]
arr[j]++;
}
}
Nicely done. We just have to optimize our code a bit further, and it will be 100pts. 
AC (100pts)
Have you thought, do we ever have to care about the exact length of the substring.
Answer
No. We are just given that it has to be a multiple of 3. Now it can be 3, 6, 9 and so on and so forth. The only condition over here is that the length has to be a multiple of 3.
So we can easily compute the starting position and ending position of substrings without even caring about its length.
Basic idea to calculate the starting positions
The ending positions are Z. So we traverse from the back (coz we have to find the starting positions, which can only be counted from the back in the problem). Suppose we encounter a Z at index i. So we increase the count of the number of Z’s in the (i % 3) position.
Why at (i % 3), and not i
Because we do not care about the length. Why not all the Z’s who have the same remainder when divided with 3, be kept in a single position.
Now, here is the tricky part. If you find an X in the index i, where (i % 3) = 0, then we do not do operations with the count of Z’s in position 0. Try counting it yourself.
Then on which position should we do the operation
The answer is, we should do the operation on ((i - 1) % 3), if i is not negative. Else we will do it on the 2nd position.
Lets see it ourselves:
1. cnt = 1; index = i, //cnt is the number of characters in the 'Good' string
2. cnt = 2; index = i + 1.
3. cnt = 3; index = i + 2.
Thus, we saw that the operations part is a bit tricky.
Now in the same way, calculate the ending position. Be careful of the tricky part.
We store the starting and ending positions in arrays, where start[i] is the number of good substrings that start from index i, and vice-versa for end[i].
Now, calculate the Minimum Importance of all the substrings, using Sliding Window.
Technique of using it
So, whenever we move one ahead, we subtract the number of ending positions at (i - k) where i is the last index of the array, in the window. We alse add the number of starting positions at i. Answer will be the minimum of all.
Solution Snippet
long long ans = 0;
for(long long i = 1; i <= k; i++) { // 1 indexing
ans += start[i]; //the number of substrings starting at i
}
for(long long i = k + 1; i <= n; i++) { // sliding window technique applied
ans = min(ans, ans - end[i - k] + start[i]); // we select the minimum of the two
}
cout << ans << endl;
TIME COMPLEXITY:
O(N) per each test case
SOLUTIONS:
Any comments on how to improve this editorial is openly welcomed!