PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: jeevanjyot
Testers: iceknight1093, rivalq
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have two strings A and B, which you can rearrange as you wish to form A' and B'.
Is it possible to make A'+B' a palindrome?
EXPLANATION:
Suppose N \leq M, i.e, A is the shorter string.
Now, suppose we’re able to obtain A' and B' such that A'+B' is a palindrome.
Since N \leq M, this means that:
- The last N characters of B' must exactly form A'.
- The remaining M - N characters of B' must form a palindrome among themselves.
Notice that this isn’t too hard to check:
- Let \text{freq}_A[c] denote the number of occurrences of c in A. Similarly define \text{freq}_B[c].
- The first condition then simply says that \text{freq}_A[c] \leq \text{freq}_B[c] for every character c from
'a'to'z'.- This can be checked quite easily by just building both frequency tables.
- The second condition requires us to check whether all the remaining characters can form a palindrome via rearrangement.
- This is a rather classical task, and has a simple solution: a list of characters can be rearranged to form a palindrome if and only if at most one of them occurs an odd number of times.
- Notice that this is also easy to check with the frequency tables we have: the number of c such that (\text{freq}_B[c] - \text{freq}_A[c]) is odd should be \leq 1.
The answer is affirmative if and only if both conditions above are satisfied.
If N \gt M just swap A and B and apply the above algorithm anyway.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++)
#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...)
#endif
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
const long long INF = 1e18;
const int N = 1e6 + 5;
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
int sumN = 0;
void solve()
{
int n = readIntSp(1, 2e5);
int m = readIntLn(1, 2e5);
sumN += n + m;
string a = readStringLn(n, n);
string b = readStringLn(m, m);
for(auto &x: a) assert(x >= 'a' and x <= 'z');
for(auto &x: b) assert(x >= 'a' and x <= 'z');
if(n > m)
swap(a, b), swap(n, m);
array<int, 26> a_cnt{}, b_cnt{};
for(auto &x: a)
a_cnt[x - 'a']++;
for(auto &x: b)
b_cnt[x - 'a']++;
bool ok = true;
int odd = 0;
for(int i = 0; i < 26; i++)
{
if(b_cnt[i] < a_cnt[i])
ok = false;
odd += (b_cnt[i] - a_cnt[i]) % 2;
}
if(odd <= 1 and ok)
cout << "YES\n";
else
cout << "NO\n";
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = readIntLn(1, 2e5);
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
assert(sumN <= 2e5);
readEOF();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
freq = {}
for c in input():
add = (n >= m) - (n < m)
if c in freq: freq[c] += add
else: freq[c] = add
for c in input():
add = (m > n) - (m <= n)
if c in freq: freq[c] += add
else: freq[c] = add
odd = 0
for y in freq.values():
odd += y%2
print('YES' if odd <= 1 and min(freq.values()) >= 0 else 'NO')
