Given a string S which is consisted of characters ‘A’, ‘B’ or ‘C’. Find the number of substrings of S which have equal number of ‘A’s, ‘B’s and ‘C’s.
EXPLANATION:
Let,
Ai = Number of ‘A’s in S between the indexes 1 and i (inclusive).
Bi = Number of ‘B’s in S between the indexes 1 and i (inclusive).
Ci = Number of ‘C’s in S between the indexes 1 and i (inclusive).
Let’s consider the substring Sj…i :
Number of ‘A’-s in that substring = Ai - Aj-1
Number of ‘B’-s in that substring = Bi - Bj-1
Number of ‘C’-s in that substring = Ci - Cj-1
So for that substring to be good: Ai - Aj-1 = Bi - Bj-1 = Ci - Cj-1
Alternatively the following two conditions are enough for that substring to be good:
Ai - Bi = Aj-1 - Bj-1
Ai - Ci = Aj-1 - Cj-1
Go from left to right and for each index i find the number of valid good substrings which ends at i. The number of such substrings would be the number of indexes k (k < i) where (Ai - Bi, Ai - Ci )= (Ak - Bk, Ak - Ck ). That can be obtained if the pair (Ak - Bk, Ak - Ck )for all k are stored in a key-value storage where the key being the pair and value being the number indexes having that difference pair. If using C++, STL Map can be used.
The author did not use a map, instead he computed all the difference pairs and then sorted those and then find the number of equal pairs.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Amazing insight you just showed me with the usage of map I still have a lot of ad-hoc thinking to do, that’s for sure
I tried to use DP to solve this problem…
I used something like:
DP[length_of_substr][start_ind][0] -> number of characters equal to A in substring s(start_ind,start_ind+size)
DP[length_of_substr][start_ind][1] -> number of characters equal to B in substring s(start_ind,start_ind+size)
DP[length_of_substr][start_ind][2] -> number of characters equal to C in substring s(start_ind,start_ind+size)
Then I tried to derive some relationships between these “DP states”, but in the end I was always getting a quadratic solution in the size of the string, i.e. O(|S|^2) and couldn’t figure out a better way of doing it…
I think the problem was that I got stuck on iterating over all sizes and for each size change the start index which would still be a quadratic solution, even if I could compute some states starting from others, for example:
DP[length_of_substr+1][0][0] = DP[length_of_substr][0][0] + 1, if the character at the (length_of_substr+1)th position is A, or we leave it as it is otherwise…
Yeah, makes sense it’s inneficient, since, as I said, I was not managing to make it run in a decent time, and, looking at it again, it makes sense why this is inneficient, is there any way of solving this using a similar approach to the one I was trying to follow?
The Editorial is good and so was the problem. what i want to ask is that how we should approach such question during the contests.After two hours of continuous thinking,I was not able to come up with this idea
What I recommend you is to solve the easier version first. This means you should come up with a solution for the AB strings. Then it’s relatively easy to find the solution for the ABC strings.
The trick to come up with the solution to the easier version is to basically write out every equation you have. For example, the condition is A_j - A_i = B_j - B_i, where A_i - A_j means the number of A characters in the range [i + 1, j]. Now play with the equation, so that we can work with it more flexible. With more experience you will realize that A_j - B_j = A_i - B_i is a good one to work with.
I still have a lot of ad-hoc thinking to do, that’s for sure 