ECR 148A : New Pallindrome Question || Solution in cpp || Question of Codeforces

 Question 


A palindrome is a string that reads the same from left to right as from right to left. For example, abacaba, aaaa, abba, racecar are palindromes.
You are given a string s consisting of lowercase Latin letters. The string s is a palindrome.
You have to check whether it is possible to rearrange the letters in it to get another palindrome (not equal to the given string s).


Input

The first line contains a single integer t (1≤t≤1000) — the number of test cases.

The only line of each test case contains a string s (2≤|s|≤50) consisting of lowercase Latin letters. This string is a palindrome.

Output

For each test case, print YES if it is possible to rearrange the letters in the given string to get another palindrome. Otherwise, print NO.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

Example

input
Copy
3
codedoc
gg
aabaa
output
Copy
YES
NO
NO
Note

In the first test case, it is possible to rearrange the letters in the palindrome codedoc to obtain the string ocdedco, which is different from the given string, but also a palindrome.

Explanation

1>. Initially Start with the test cases, take test cases

2> Take input as a string as mentioned in the question.

3>

Base Logic 

count all the character in the string and store in a map

if() -> all the character count all even and only one character count is applicable if it is odd

and other all cases are false they will generate No as a answer.

Code

#include<bits/stdc++.h>

using namespace std;


#define test     long long T;cin>>T;while(T--)

#define all(x) (x).begin(), (x).end()


// C. Mr. Perfectly Fine 871 Div 4

vector<int> sumOfDigits(int n){


  vector<int> vec;


  return vec;

}



void solve()

{

   string s; cin>>s;

   map<char,int> mp;

   for(int i=0;i<s.size();i++){

        mp[s[i]]++;

   }

   if(s.size()%2==0){

      int cnt=0;

      if(mp.size()==1) {cout<<"NO"<<endl; return; }

      else {

        for(auto it : mp){

            if(it.second%2 != 0){

                cout<<"NO"<<endl;

                return;

            }

        }

      }

   }

   else{

      int cnt=0;

      if(mp.size()<2) {cout<<"NO"<<endl; return; }

      else if(mp.size()==2){

        for(auto it : mp){

            if(it.second==1) {

                cout<<"NO"<<endl;

                return;

            }

        }

      }

      else {

        for(auto it : mp){

            if(it.second%2 != 0) cnt++;

        }

        if(cnt>1){

            cout<<"NO"<<endl;

            return;

        }

      }

   }

   cout<<"YES"<<endl;

}




signed main() {

    test

    //(if you want to take the more test cases you may uncomment it out)

    solve();

}

Previous Post Next Post