← 返回题目列表

Codeforces · 1216/A

A. 前缀

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

Nikolay 得到了一个长度为 $$$n$$$ 的字符串 $$$s$$$,该字符串仅由小写拉丁字母“a”和“b”组成。其仓位编号从 $$$1$$$ 到 $$$n$$$。

他想要修改他的字符串,以便其每个偶数长度的前缀都具有相同数量的字母“a”和“b”。为了实现这一点,Nikolay 可以执行以下操作任意次数(可能为零):选择字符串中的某个位置并将该位置上的字母替换为另一个字母(即用“b”替换“a”或用“a”替换“b”)。尼古拉不能使用除“a”和“b”之外的任何字母。

长度为 $$$l$$$ ($$$1 \le l \le n$$$) 的字符串 $$$s$$$ 的前缀是字符串 $$$s[1..l]$$$。

例如,对于字符串$$$s=$$$"abba",有两个偶数长度的前缀。第一个是$$$s[1\dots2]=$$$"ab",第二个$$$s[1\dots4]=$$$"abba"。它们都有相同数量的“a”和“b”。

你的任务是计算 Nikolay 必须对字符串 $$$s$$$ 执行的最少操作次数来修改它,以便其每个偶数长度的前缀都具有相等数量的字母“a”和“b”。

输入

输入的第一行包含一个偶数 $$$n$$$ $$$(2 \le n \le 2\cdot10^{5})$$$ — 字符串 $$$s$$$ 的长度。

输入的第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,该字符串仅由小写拉丁字母“a”和“b”组成。

输出

在第一行中,打印 Nikolay 必须对字符串 $$$s$$$ 执行的最少操作数以对其进行修改,以便其每个偶数长度的前缀都具有相等数量的字母“a”和“b”。

在第二行中打印 Nikolay 在应用所有操作后获得的字符串。如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

4
bbbb

输出 #1

2
abba

输入 #2

6
ababab

输出 #2

0
ababab

输入 #3

2
aa

输出 #3

1
ba

注意

在第一个示例中,Nikolay 必须执行两个操作。例如,他可以将第一个“b”替换为“a”,将最后一个“b”替换为“a”。

在第二个示例中,Nikolay 不需要执行任何操作,因为初始字符串的偶数长度的每个前缀已经包含相同数量的字母“a”和“b”。