AB Balance
Contest: Educational Codeforces Round 116 (Rated for Div. 2)
Difficulty rating: 900
Tags: strings

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
4
b
aabbbabaa
abbb
abbaab

Example output:
b
aabbbabaa
bbbb
abbaaa

Editorial:
Let's look at the first and the last characters of $$$s$$$. Note that if $$$s_1 = s_n$$$ (where $$$n = |s|$$$), then $$$\operatorname{AB}(s)$$$ is always equal to $$$\operatorname{BA}(s)$$$.
It can be proved, for example, by induction: if $$$s$$$ consists of equal characters then $$$\operatorname{AB}(s) = \operatorname{BA}(s) = 0$$$; if $$$s$$$ has a structure like abb...ba (or baa...ab) then $$$\operatorname{AB}(s) = \operatorname{BA}(s) = 1$$$.
Otherwise, there is at least one character $$$s_i$$$ in the middle that equal to $$$s_1$$$ and $$$s_n$$$. So we can split string $$$s$$$ in $$$s[1..i]$$$ and $$$s[i..n]$$$. Both these string has $$$\operatorname{AB} = \operatorname{BA}$$$ (by induction), so our string $$$s$$$ also has $$$\operatorname{AB}(s) = \operatorname{BA}(s)$$$.
As a result, if $$$s_1 = s_n$$$ then the answer is $$$0$$$, and we print the string untouched. Otherwise, we replace either $$$s_1$$$ or $$$s_n$$$ and get the desired string.
(It also can be proved that if $$$s_1 \neq s_n$$$ then $$$\operatorname{AB}(s) \neq \operatorname{BA}(s)$$$)