PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Kanhaiya Mohan
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
1102
PREREQUISITES:
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)