Hello! For this problem, why do we add up the prefix of length a−1 and the suffix of length N−b? What’s the point of getting the suffix? I feel like there’s a really obvious reason but I’m just not seeing it… Thanks in advance!
What do you mean by “add up”?
Consider the following test case:
8 2
ABBAABCB
3 6
1 4
As you may be able to recognize, this is the sample test case… Let’s just consider the first query only since the latter will be similar to the previous.
The first query is excluding the substring “BAAB”. Therefore, AB and CB are left. However, these two substrings are disjoint (meaning they have to be considered independently). Therefore, you have to check how many colors of paint are to the left of substring “BAAB” (prefix), and you have to check how many colors of paint are needed to the right of the substring “BAAB” (suffix).
In the above case, the prefix leading up to index 2 is 2 and the suffix ending at index 7 is 2, and the sum of the prefix sum and the suffix sum is 4 which is the provided output.
The reason why we need prefix/suffix sums is to compute the minimum number of strokes of paint in O(1) time for each query.
I see, that was very helpful. Thanks!