Algorithm
You are given a string s of length n consisting of characters a and/or b.
Let AB(s) be the number of occurrences of string ab in s as a substring. Analogically, 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 si with character a or b.
What is the minimum number of steps you need to make to achieve AB(s)=BA(s)?
Reminder:
The number of occurrences of string d in s as substring is the number of indices i (1≤i≤|s|−|d|+1) such that substring sisi+1…si+|d|−1 is equal to d. For example, 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≤t≤1000). Description of the test cases follows.
The first and only line of each test case contains a single string s (1≤|s|≤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 AB(s)=BA(s) you'll get making the minimum number of steps.
If there are multiple answers, print any of them.
4 b aabbbabaa abbb abbaab
b aabbbabaa bbbb abbaaa
In the first test case, both AB(s)=0 and BA(s)=0 (there are no occurrences of ab (ba) in b), so can leave s untouched.
In the second test case, AB(s)=2 and BA(s)=2, so you can leave s untouched.
In the third test case, AB(s)=1 and BA(s)=0. For example, we can change s1 to b and make both values zero.
In the fourth test case, AB(s)=2 and BA(s)=1. For example, we can change s6 to a and make both values equal to 1.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
string s;
cin>>s;
if(s[0] == s[s.length() - 1]){
cout<<s<<endl;
}
else{
s[0] = s[s.length() - 1];
cout<<s<<endl;
}
}
}Input
b
aabbbabaa
abbb
abbaab
Output
aabbbabaa
bbbb
abbaaa
Demonstration
Codeforcess Solution 1606-A A. AB Balance ,C++, Java, Js and Python ,1606-A,Codeforcess Solution