← 返回题目列表

Codeforces · 1606/A

A. AB 平衡

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

给定一个字符串 $$$s$$$,长度为 $$$n$$$,由字符 a 和/或 b 组成。

令 $$$\operatorname{AB}(s)$$$ 为字符串 ab 在 $$$s$$$ 中作为子字符串出现的次数。类似地,$$$\operatorname{BA}(s)$$$ 是 ba 作为子串在 $$$s$$$ 中出现的次数。

在一步中,您可以选择任何索引 $$$i$$$ 并将 $$$s_i$$$ 替换为字符 a 或 b。

要实现 $$$\operatorname{AB}(s) = \operatorname{BA}(s)$$$,您需要执行的最少步骤是多少?

提醒:

字符串 $$$d$$$ 在 $$$s$$$ 中作为子字符串出现的次数是索引 $$$i$$$ ($$$1 \le i \le |s| - |d| + 1$$$) 的数量,使得子字符串 $$$s_i s_{i + 1} \dots s_{i + |d| - 1}$$$ 等于$$$d$$$。例如,$$$\operatorname{AB}($$$aabbbabaa$$$) = 2$$$,因为有两个索引 $$$i$$$:$$$i = 2$$$,其中 aabbbabaa 和 $$$i = 6$$$,其中 aabbbabaa.

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含单个字符串 $$$s$$$ ($$$1 \le |s| \le 100$$$,其中 $$$|s|$$$ 是字符串 $$$s$$$ 的长度),仅包含字符 a 和/或 b。

输出

对于每个测试用例,使用 $$$\operatorname{AB}(s) = \operatorname{BA}(s)$$$ 打印结果字符串 $$$s$$$,您将获得最少的步骤数。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

4
b
aabbbabaa
abbb
abbaab

输出 #1

b
aabbbabaa
bbbb
abbaaa

注意

在第一个测试用例中, $$$\operatorname{AB}(s) = 0$$$ 和 $$$\operatorname{BA}(s) = 0$$$ (b 中没有出现 ab (ba)),因此可以保持 $$$s$$$ 不变。

在第二个测试用例中,$$$\operatorname{AB}(s) = 2$$$ 和 $$$\operatorname{BA}(s) = 2$$$,因此您可以保持 $$$s$$$ 不变。

在第三个测试用例中,$$$\operatorname{AB}(s) = 1$$$ 和 $$$\operatorname{BA}(s) = 0$$$。例如,我们可以将 $$$s_1$$$ 更改为 b 并将两个值都设置为零。

在第四个测试用例中,$$$\operatorname{AB}(s) = 2$$$ 和 $$$\operatorname{BA}(s) = 1$$$。例如,我们可以将 $$$s_6$$$ 更改为 a 并使两个值都等于 $$$1$$$。