# PROBLEM LINK:

Author: Shahjalal Shohag

Tester: Ildar Gainullin

Editorialist: Rajarshi Basu

# DIFFICULTY:

Cakewalk

# PREREQUISITES:

Implementation

# PROBLEM:

You are given a string S with length N \leq 1000. You may perform the following operation any number of times: choose a non-empty substring of S (possibly the whole string S) such that each character occurs an even number of times **in this substring** and erase this substring from S. (The parts of S before and after the erased substring are concatenated and the next operation is performed on this shorter string.) Is it possible to erase the whole string using one or more operations?

# EXPLANATION:

Let us see what we are trying to do in every operation. We are taking

* even number of occurrences of some of the letters* of the string (which happen to be a substring but this shouldnâ€™t bother us too much) and are

*them. Therefore the parity of the frequency of the characters do not change.*

**deleting**Now, what if the all the characters in the string S had even number of occurrences? We could have taken the entire string right? Okayâ€¦ that was easy.

Now what if some character occurs an odd number of times. Then, however many number of operations we performed, we could never delete all occurrences of that number right? I mean, letâ€™s say the number â€™aâ€™ had 5 occurrences. After two operations, maybe we removed 4 of them. But note that we can never remove all 5 since we cannot pair odd number of occurrences in any particular reduction.

So essentially, if any character is present odd number of times, the answer is NO, else the answer is YES.

# SOLUTION:

## Setterâ€™s Code

```
#include<bits/stdc++.h>
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
assert(1 <= t && t <= 200);
while (t--) {
int n; cin >> n;
string s; cin >> s;
assert(n == s.size());
assert(1 <= s.size() && s.size() <= 1000);
for (auto c: s) assert('a' <= c && c <= 'z');
int mask = 0;
for (auto c: s) mask ^= 1 << (c - 'a');
if (mask) cout << "NO\n";
else cout << "YES\n";
}
return 0;
}
```