Hello CF family, I attempted to solve the Palindrome Pair problem last night. I had to look at the editorial and then the solution to the problem after failing several times. I attempted in O(N2) and received TLE in the 9th TC.
void solve()
{
int n;
cin >> n;
vector<string> v(n);
loop(n)
{
cin >> v[i];
}
map<pair<string, string>, bool> store;
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j =i+1; j < n; j++)
{
if (i != j)
{
string a = v[i];
string b = v[j];
// if (store.count({a, b}) == 0 or store.count({b,a})==0)
// {
if (isPalin((a + b)))
{
ans++;
}
else
{
map<char, int> m;
loop(a.size())
{
m[a[i]]++;
}
loop(b.size())
{
m[b[i]]++;
}
int cnt = 0;
for (auto x : m)
{
if (x.second % 2 != 0)
{
cnt++;
}
}
if (cnt <= 1)
ans++;
}
// }
// store[{a, b}] = true;
// store[{b, a}] = true;
}
}
}
// ans /= 2;
cout << ans << '\n';
// debug(store);
}
But I didn't catch the idea of using the bit mask here, nor did I get the problem's editorial. So I'm seeking for someone to help me with this problem.
Thanks ( in advance )







