Can someone please explain the below solution?
Problem Statement -
Hyperdrome is a string that has at most one letter occurring odd times. Find number of hyperdrome substrings in a given string.
Example -
Input: "aabb"
Output: [a, aa, aab, aabb, abb, b, bb]
Solution - Link
After analysing the slide above and code below, I could not understand the purpose of the for loop. I have commented section of code that I was able to understand.
Looking forward to some help in understanding this alogorithm!
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
long long answer = 0;
string s;
cin >> s;
map<int, int> m;
m[0] = 1;
int x = 0;
for (auto& c : s) {
// 1 << d converts string to corresponding binary representation
// by using XOR we set or unset the bits
// 0 indicates even occurrences and 1 indicates odd occurrences of any characters a - z
int d = c - '0';
x = x ^ (1 << d);
answer = answer + m[x];
for (int i = 0; i < 26; ++i) {
answer = answer + m[x ^ (1 << i)];
}
++m[x];
}
cout << answer << endl;
return 0;
}Comments (3)