← 返回题目列表

Codeforces · 1108/D

D. 多样化的花环

中文机器翻译题面 查看原题

你有一个由 $$$n$$$ 灯组成的花环。每盏灯的颜色分别为红色、绿色或蓝色。第 $$$i$$$ 灯的颜色是 $$$s_i$$$(“R”、“G”和“B”——花环中灯的颜色)。

你必须对这个花环中的一些灯重新着色(重新着色灯意味着将其初始颜色更改为另一种颜色),这样获得的花环是多样化的。

如果任意两个相邻(连续)的灯(即位置之间的距离为 $$$1$$$ 的灯)具有不同的颜色,则该花环被称为多样化。

换句话说,如果获得的花环是$$$t$$$,那么对于从$$$1$$$到$$$n-1$$$的每个$$$i$$$,应该满足条件$$$t_i \ne t_{i + 1}$$$。

在对初始花环重新着色以使其多样化的所有方法中,您必须选择一种重新着色灯数量最少的方法。如果有多个最优解,则打印其中任意一个。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 灯的数量。

输入的第二行包含字符串 $$$s$$$,由 $$$n$$$ 字符“R”、“G”和“B”组成 - 花环中灯的颜色。

输出

在输出的第一行打印一个整数 $$$r$$$ — 从给定花环获得多样化花环所需的最小重新着色次数。

在输出的第二行中打印一个长度为 $$$n$$$ 的字符串 $$$t$$$ — 从第一个花环中以最少的重新着色次数获得的多样化花环。如果有多个最优解,则打印其中任意一个。

示例

输入 #1

9
RBGRRBRGG

输出 #1

2
RBGRGBRGR

输入 #2

8
BBBGBRRR

输出 #2

2
BRBGBRGR

输入 #3

13
BBRRRRGGGGGRR

输出 #3

6
BGRBRBGBGBGRG