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] , we can add to the total, If the frequency difference ever becomes , we can break and skip to the next R index.
Time Complexity:
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[] is the number of R's from Rfreq[G[]] to Rfreq[G[]] if they exist, multiplied by the number of B's from Bfreq[G[]] to Bfreq[G[]] if they exist.
Time Complexity: