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.
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] -> number of characters equal to A in substring s(start_ind,start_ind+size)
DP[length_of_substr][start_ind] -> number of characters equal to B in substring s(start_ind,start_ind+size)
DP[length_of_substr][start_ind] -> 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] = DP[length_of_substr] + 1, if the character at the (length_of_substr+1)th position is A, or we leave it as it is otherwise…
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