Nice Garland 一个三个字符连续的问题（思）

problem description

You have a garland consisting of n lamps. Each lamp is colored red, green or blue. The color of the i-th lamp is si (‘R’, ‘G’ and ‘B’ — colors of lamps in the garland).

You have to recolor some lamps in this garland (recoloring a lamp means changing its initial color to another) in such a way that the obtained garland is nice.

A garland is called nice if any two lamps of the same color have distance divisible by three between them. I.e. if the obtained garland is t, then for each i,j such that ti=tj should be satisfied |i−j| mod 3=0. The value |x| means absolute value of x, the operation x mod y means remainder of x when divided by y.

For example, the following garlands are nice: “RGBRGBRG”, “GB”, “R”, “GRBGRBG”, “BRGBRGB”. The following garlands are not nice: “RR”, “RGBG”.

Among all ways to recolor the initial garland to make it nice you have to choose one with the minimum number of recolored lamps. If there are multiple optimal solutions, print any of them.

Input

The first line of the input contains one integer n (1≤n≤2⋅105) — the number of lamps.

The second line of the input contains the string s consisting of n characters ‘R’, ‘G’ and ‘B’ — colors of lamps in the garland.

Output

In the first line of the output print one integer r — the minimum number of recolors needed to obtain a nice garland from the given one.

In the second line of the output print one string t of length n — a nice garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.

Examples

Input

3
BRB

Output

1
GRB

Input

7
RGBGRBB

Output

3
RGBRGBR

手记：昨天晚上比较累，大约11点就上床了，看了一小会B站，看到一个好看的二次元的角色，红衣服长着小红角，于是就去搜搜看看，原来这个小姐姐叫02，那天晚上肝到了两点看02也就是darling，哇哇哇，02也太可爱了吧，瞬间被粉啊，（虽然很好看，但是我要忘了你呢，我要专注算法呢，别生气02，我给你蜂蜜吃~）。我当后要更加的努力学习算法，一定要做出一点样子，找一个像 02 的小姐姐当女朋友，我要去南方，去大城市，我有太多期盼的东西，也背负着很多希望，现在的我虽然很努力，但是依然很弱鸡。每天都积累一点，身在一个普通二本学校，就更加需要我拿出更多时间与精力，未来加油！（我不管02 是我老婆）手动狗头。

题意：给定一个字符串，字符串中只存在三个字母，要求每两个相同的字母之间的距离能够被3整除。

历程：刚开始看到这道题的时候还没有思路呢，看了前两个题，也没有思路，怎么办啊，我不想爆零啊，于是我就跑到了家里的小黑屋里，在里边静静的想题，奈何02小姐姐太美了，思路好几次被02打断，（好吧，看在02这么好看的份上就原谅你啦），突然我意识到一件事情，这个字符种类是 3 个， 如果想每两个相同的字母之间都有 2 + 个字母，那肯定就是跟这个不同的另外两个了呗，不能再多了啦，哈哈，我立马跑到卧室，去解决这道题。第一次还RE了。。原因是数组开小了，下次一定不能这样了， 嗯，一定！

代码↓

看起来这样不是很简洁呢，不过这个代码思路很简单呢~

#include <iostream>

using namespace std;

const int N = 301000;
char str[N], t[3] = { 'R', 'G', 'B' };
int ans[3], res = 0x3f3f3f3f;
int main()
{
	int n; cin >> n;
	scanf("%s", str);
	if (n <= 2)
	{
		if (str[1] != str[0]) printf("0n%s", str);

		else
		{
			for (int i = 0; i < 3; i++)
			{
				if (t[i] == str[0])
				{
					printf("1n%c%c", str[0], t[(i + 1) % 3]);
				}
			}
		}	
		return 0;
	}
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (i == j) continue;
			for (int k = 0; k < 3; k++)
			{
				if (k == j || k == i) continue;
				//cout << i << j << k << endl;
				char a[3] = { t[i], t[j], t[k] };
				int sum = 0;
				for (int r = 0; r < n; r++)
				{
					int ts = r % 3;
					if (a[ts] != str[r]) sum++;
				}
				//cout << sum << endl;
				if (sum < res)
				{
					ans[0] = i, ans[1] = j, ans[2] = k;
					res = sum;
				}
			}
		}
	}
	printf("%dn", res);

	for (int i = 0; i < n; i++)
	{
		printf("%c", t[ans[i % 3]]);
	}
}

最后

以上就是顺利大雁为你收集整理的Nice Garland 一个三个字符连续的问题（思）的全部内容，希望文章能够帮你解决Nice Garland 一个三个字符连续的问题（思）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。