Making Anagrams

See the original problem on HackerRank.

Solutions

Two strings are anagrams of one another if they share the same characters and each character has the same frequency in both strings. Thus, we can easily solve this problem with a frequency table.

Basically, we can add 1 for each character in a and subtract 1 for each character in b. Those characters with non-zero frequency must be deleted and then added to the total count.

Here is an implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
string a, b; cin >> a >> b;
array<int, 26> histogram{};

for (auto c : a)
    histogram[c-'a']++;

for (auto c : b)
    histogram[c-'a']--;

auto chars = 0;
for (auto i : histogram)
{
    chars += abs(i);
}
cout << chars;

The reduce pattern brings out thus the third for loop can be replaced with:

1
2
3
cout << accumulate(begin(histogram), end(histogram), 0, [](int curr, int nxt){
   return nxt != 0 ? curr + abs(nxt) : curr;
});

Just for fun, here is a possible implementation of the same call to accumulate with C++20 ranges:

1
cout << ranges::accumulate( f | view::transform([](auto i) { return abs(i); }), 0 ) ;
We've worked on this challenge in these gyms: modena 
comments powered by Disqus