**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!