# ABSTRING - Editorial

Author: Kanhaiya Mohan
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh

1102

None

# PROBLEM:

There is a string of length S, and two strings A and B. Alice and Bob alternate moves, as follows:

• Alice, on her turn, removes one character from S and appends it to A.
• Bob, on his turn, removes one character from S and appends it to B.

This is done as long as S is non-empty. Via some sequence of moves, can A be made equal to B in the end?

# EXPLANATION:

A and B together contain all the characters of S.
If A = B in the end, then every character of A has a ‘copy’ of itself lying in S.

This can only happen when every type of character appears an even number of times in S, i.e,

• There are an even number of a-s
• There are an even number of b-s
• There are an even number of c-s
\vdots
• There are an even number of z-s

So, simply check whether S satisfies this condition (by, for example, iterating across all 26 characters and finding their counts in S), and answer “Yes” or “No” appropriately.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Editorialist's code (Python)
import collections
for _ in range(int(input())):
n = int(input())
s = input()
d = collections.Counter(s)
ans = 'Yes'
for x in d.values():
if x%2 == 1:
ans = 'No'
print(ans)