# String Game || codechef solution

## Problem

Alice and Bob are playing a game. They have a common string $�$ of length $�$. The players also have their individual strings $�$ (belonging to Alice) and $�$ (belonging to Bob) which are empty in the beginning. Game begins with Alice and both players take alternate turns.

In her/his turn, the player picks a single character from string $�$, adds it to the end of their individual string and deletes the picked character from string $�$.

The game continues until string $�$ is empty. Find whether there exists a sequence of moves such that the strings $�$ and $�$ are same at the end of the game.

### Input Format

• The first line of input will contain a single integer $�$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains an integer $�$ — the length of the string.
• The next line contains the strings $�$ consisting of lowercase english alphabets.

### Output Format

For each test case, output on a new line, YES if there exists a sequence of moves such that the strings $�$ and $�$ are same at the end of the game, and NO otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings YESyEsyes, and yeS will all be treated as identical).

### Constraints

• $1\le �\le 1{0}^{3}$
• $1\le �\le 1{0}^{5}$
• $�$ consists of lowercase english alphabets
• The sum of $�$ over all test cases does not exceed $2\cdot 1{0}^{5}$.

### Sample 1:

Input
Output
4
4
abab
5
cbcba
4
abcd
6
pqprqr

YES
NO
NO
YES

### Explanation:

Test case $1$: Consider the following sequence of moves:

• Alice picks the first character of string $�$ and adds it to the end of string $�$. Thus, $�$ becomes bab and $�$ becomes a.
• Bob picks the second character of string $�$ and adds it to the end of string $�$. Thus, the strings are $�=$ bb$�=$ a, and $�=$ a .
• Alice picks the second character of string $�$ and adds it to the end of string $�$. Thus, the strings are $�=$ b$�=$ ab, and $�=$ a .
• Bob picks the first character of string $�$ and adds it to the end of string $�$. Thus, $�$ becomes empty, $�=$ ab, and $�=$ ab .

We can see that using this sequence of moves, the final strings $�$ and $�$ are equal.

Test case $2$: There exists no sequence of moves such that the strings $�$ and $�$ become equal in the end.

Test case $3$: There exists no sequence of moves such that the strings $�$ and $�$ become equal in the end.

Test case $4$: Consider the following sequence of moves:

• Alice picks the first character of string $�$ and adds it to the end of string $�$. Thus, $�$ becomes qprqr and $�$ becomes p.
• Bob picks the second character of string $�$ and adds it to the end of string $�$. Thus, the strings are $�=$ qrqr$�=$ p, and $�=$ p .
• Alice picks the second character of string $�$ and adds it to the end of string $�$. Thus, the strings are $�=$ qqr$�=$ pr, and $�=$ p .
• Bob picks the third character of string $�$ and adds it to the end of string $�$. Thus, $�$ becomes qq$�$ becomes pr, and $�$ becomes pr.
• Alice picks the second character of string $�$ and adds it to the end of string $�$. Thus, the strings are $�=$ q$�=$ prq, and $�=$ pr .
• Bob picks the first character of string $�$ and adds it to the end of string $�$. Thus, $�$ becomes empty, $�=$ prq, and $�=$ prq .

We can see that using this sequence of moves, the final strings $�$ and $�$ are equal.

Code(c++):-

#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
if(n%2!=0)
cout<<"NO"<<endl;
else
{
int fre[26]={0};
for(int i=0;i<n;i++)
{
fre[s[i]-97]+=1;
}
int flag=0;
for(int i=0;i<26;i++)
{
if(fre[i]%2!=0)
{
flag=1;
break;
}
}
if(flag==0)
cout<<"YES"<<endl;
else

cout<<"NO"<<endl;
}
}
return 0;
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-