Given a string consisting of letters, 'a',
'b' and 'c', we can perform the following operation: Take any two adjacent
distinct characters and replace them with the third character. For example, if
'a' and 'b' are adjacent, they can be replaced by 'c'. Find the smallest string
which we can obtain by applying this operation repeatedly.
Input Format
The first line contains the number of test
cases T. T test cases follow. Each test case contains the string you
start with.
Constraints
1 <=T<=100
The string will have at most 100
characters.
Output Format
Output T lines, one for each test case,
containing the smallest length of the resultant string after applying the
operations optimally.
Sample Input
3
cab
bcab
ccccc
Sample Output
2
1
5
Explanation
For the first
case, you can either get cab-> cc or cab-> bb, resulting in a
string of length 2.
For the second
case, one optimal solution is: bcab-> aab-> ac-> b. No more operations
can be applied and the resultant string has length 1.
For the third
case, no operations can be performed. So, the answer is 5.
Solution:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
string s;
cin>>s;
int a=count(s.begin(),s.end(),'a');
int b=count(s.begin(),s.end(),'b');
int c=count(s.begin(),s.end(),'c');
if(a==0&&b==0||b==0&&c==0||c==0&&a==0)
cout<<s.length()<<endl;
else if(a%2==0&&b%2==0&&c%2==0||a%2==1&&b%2==1&&c%2==1)
cout<<"2"<<endl;
else
cout<<"1"<<endl;
}
}