Editorial for Mock CCC '24 Contest 1 J3 - RGB Words

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: htoshiro

To solve this problem, we aim to count the number of "RGB-words" present in a given string.

Subtask 1 and 2 This subtask can be solved using simple brute force. We can store the indices or the R's and B's, and store the number of G's in a frequency array. We can loop through all the R indices and loop through the B indices. If the B index is greater than the R index and freq[B index] - freq[R index] = 1, we can add to the total, If the frequency difference ever becomes > 1, we can break and skip to the next R index.
Time Complexity: \mathcal{O}(N^2)
Subtask 3 The final optimization is to use frequency arrays for R's and B's and to store the indices of the G's. We can realize that the number of RGB-words containing the G[i] is the number of R's from Rfreq[G[i - 1]] to Rfreq[G[i]] if they exist, multiplied by the number of B's from Bfreq[G[i]] to Bfreq[G[i + 1]] if they exist.
Time Complexity: \mathcal{O}(N)

Comments