A14761. AB Balance
编程题
普及/提高-
知识点
题目描述
You are given a string $s$ of length $n$ consisting of characters a and/or b.
Let $\operatorname{AB}(s)$ be the number of occurrences of string ab in $s$ as a substring. Analogically, $\operatorname{BA}(s)$ is the number of occurrences of ba in $s$ as a substring.
In one step, you can choose any index $i$ and replace $s_i$ with character a or b.
What is the minimum number of steps you need to make to achieve $\operatorname{AB}(s) = \operatorname{BA}(s)$ ?
Reminder:
The number of occurrences of string $d$ in $s$ as substring is the number of indices $i$ ( $1 \le i \le |s| - |d| + 1$ ) such that substring $s_i s_{i + 1} \dots s_{i + |d| - 1}$ is equal to $d$ . For example, $\operatorname{AB}($ aabbbabaa $) = 2$ since there are two indices $i$ : $i = 2$ where aabbbabaa and $i = 6$ where aabbbabaa.
Let $\operatorname{AB}(s)$ be the number of occurrences of string ab in $s$ as a substring. Analogically, $\operatorname{BA}(s)$ is the number of occurrences of ba in $s$ as a substring.
In one step, you can choose any index $i$ and replace $s_i$ with character a or b.
What is the minimum number of steps you need to make to achieve $\operatorname{AB}(s) = \operatorname{BA}(s)$ ?
Reminder:
The number of occurrences of string $d$ in $s$ as substring is the number of indices $i$ ( $1 \le i \le |s| - |d| + 1$ ) such that substring $s_i s_{i + 1} \dots s_{i + |d| - 1}$ is equal to $d$ . For example, $\operatorname{AB}($ aabbbabaa $) = 2$ since there are two indices $i$ : $i = 2$ where aabbbabaa and $i = 6$ where aabbbabaa.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 1000$ ). Description of the test cases follows.
The first and only line of each test case contains a single string $s$ ( $1 \le |s| \le 100$ , where $|s|$ is the length of the string $s$ ), consisting only of characters a and/or b.
The first and only line of each test case contains a single string $s$ ( $1 \le |s| \le 100$ , where $|s|$ is the length of the string $s$ ), consisting only of characters a and/or b.
输出格式
For each test case, print the resulting string $s$ with $\operatorname{AB}(s) = \operatorname{BA}(s)$ you'll get making the minimum number of steps.
If there are multiple answers, print any of them.
If there are multiple answers, print any of them.
输入输出样例
输入 #1
4 b aabbbabaa abbb abbaab
输出 #1
b aabbbabaa bbbb abbaaa
说明/提示
In the first test case, both $\operatorname{AB}(s) = 0$ and $\operatorname{BA}(s) = 0$ (there are no occurrences of ab (ba) in b), so can leave $s$ untouched.
In the second test case, $\operatorname{AB}(s) = 2$ and $\operatorname{BA}(s) = 2$ , so you can leave $s$ untouched.
In the third test case, $\operatorname{AB}(s) = 1$ and $\operatorname{BA}(s) = 0$ . For example, we can change $s_1$ to b and make both values zero.
In the fourth test case, $\operatorname{AB}(s) = 2$ and $\operatorname{BA}(s) = 1$ . For example, we can change $s_6$ to a and make both values equal to $1$ .
In the second test case, $\operatorname{AB}(s) = 2$ and $\operatorname{BA}(s) = 2$ , so you can leave $s$ untouched.
In the third test case, $\operatorname{AB}(s) = 1$ and $\operatorname{BA}(s) = 0$ . For example, we can change $s_1$ to b and make both values zero.
In the fourth test case, $\operatorname{AB}(s) = 2$ and $\operatorname{BA}(s) = 1$ . For example, we can change $s_6$ to a and make both values equal to $1$ .