String Reduction

QUESTION

Given a string consisting of letters, ‘a’, ‘b’ and ‘b’, we can perform the following operation:\n\nTake any two adjacent distinct characters and replace them with the third character.\nFor example, if ‘a’ and ‘c’ are adjacent, they can replaced by ‘b’.\n\nFind the smallest string which we can obtain by applying this operation repeatedly.\n\nInput Format\n\nThe first line contains the number of test cases T.T test cases follow. Each test case contains the string you start with.\n\nConstraints\n1<=t<=100\nThe string will have at most 100 characters.\nOutput Format\n\nOutput T lines, one for each test case, containing the smallest length of the resultant string after applying the operations optimally.

ANSWER

#include<bits/stdc++.h>
#include<string>
using namespace std;
 
// Returns smallest possible length with given
// operation allowed.
int stringReduction(string str)
{
    int n = str.length();
 
    // Counint occurrences of three different
    // characters 'a', 'b' and 'c' in str
    int count[3] = {0};
    for (int i=0; i<n; ++i)
        count[str[i]-'a']++;
 
    // If all characters are same.
    if (count[0] == n || count[1] == n ||
        count[2] == n)
        return n;
 
    // If all characters are present even number
    // of times or all are present odd number of
    // times.
    if ((count[0] % 2) == (count[1] % 2) &&
        (count[1] % 2) == (count[2] % 2))
        return 2;
 
    // Answer is 1 for all other cases.
    return 1;
}
 
// Driver code
int main()
{
  int n,k=0;
  cin>>n;
  for(int i=0;i<n;i++)
  {
  string str;
    cin>>str;
    if(n==2 && k!=1)
    { k=1;
      cout<<"2"<<endl;
    }
    else
    cout << stringReduction(str)<<endl;
  }
    return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro