Mock CCC '24 Contest 1 J3 - RGB Words - Olympiads Online Judge

Mock CCC '24 Contest 1 J3 - RGB Words

Points: 5 (partial)

Time limit: 1.0s

Memory limit: 512M

Author:

Problem type

Tommy likes the RGB keyboard. He would like to see how many RGB-words are in a given string $s$ ~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$ ~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$ ~N~, denoting the length of the given string $s$ ~s~.

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

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

Marks Awarded	$N$ ~N~
$3$ ~3~ marks	$1 \leq N \leq 500$ ~1 \leq N \leq 500~
$3$ ~3~ marks	$1 \leq N \leq 5000$ ~1 \leq N \leq 5000~
$9$ ~9~ marks	$1 \leq N \leq 10^6$ ~1 \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$ ~s~.

Sample Input 1

4
RBGB

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

5
RGBAB

Sample Output 2

Explanation for Sample 2

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

Sample Input 3

4
RGGB

Sample Output 3

Comments

0

Little_giraffe07745 commented on Sept. 27, 2025, 2:36 a.m.

Be sure to test hard ones like RRGBB and RGRGB.

0

aidanLa commented on Jan. 23, 2025, 9:09 p.m.

Is there a way to solve this with regular expressions?