Mock CCC '24 Contest 1 J3 - RGB Words

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Tommy likes the RGB keyboard. He would like to see how many RGB-words are in a given string s. An RGB-word is defined as a substring that starts with an R and ends with a B, and between this R and the B letter G appears exactly once. For example, RGB, and RAGB are RGB-words. However, RGGB is not an RGB-word. You are given a string s, Tommy would like to know how many RGB-words are there in the string, can you write a program to help him?

Input Specification

The first line contains an integer N, denoting the length of the given string s.

The second line contains the given string s, consisting of only capital English letters.

The following table shows how the available 15 marks are distributed.

Marks AwardedN
3 marks1 \leq N \leq 500
3 marks1 \leq N \leq 5000
9 marks1 \leq N \leq 10^6

Output Specification

The first and only line of output contains a single integer, representing the number of RGB-words found in the given string s.

Sample Input 1


Sample Output 1


Explanation for Sample 1

RBGB is the only RGB-word that occurs in this case. Note that RB is not an RGB-word.

Sample Input 2


Sample Output 2


Explanation for Sample 2

RGB and RGBAB are RGB-words. Thus, there are a total of 2 RGB-words in the given string s.

Sample Input 3


Sample Output 3



There are no comments at the moment.