Making Anagrams · Coding Gym

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 ) ;

An alternative solution consists in using a set operation to calculate the symmetric difference between the two strings: the symmetric difference between two sets is the set of all those elements which belongs either to the first one or to the second one but not to both.

It’s important to take into accounts multiple occurrences of elements. In C++ we can use set_symmetric_difference because it does it by design:

1
2
3
4
5


sort(begin(s1), end(s1));
sort(begin(s2), end(s2));
vector<char> res;
set_symmetric_difference(begin(s1), end(s1), begin(s2), end(s2), back_inserter(res));
cout << res.size();

(the additional storage is not really needed: we might create a fake output iterator which just increment a counter).

An alternative approach, using a 2-pointer technique, has been developed by Andrea Battistello and Lucio Grenzi:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


function makingAnagrams(s1, s2) {
    var s3 = s1.split("");
    var s4 = s2.split("");
    s3.sort();
    s4.sort();
    var i = 0;
    var j = 0;
    var count = 0;
    while ((i <= s3.length) && (j <= s4.length))
    {
        if (i >= s3.length) {
            count++;
            j++;
        }
        else if (j >= s4.length) {
            count++;
            i++;
        }
        else if (s3[i] == s4[j]) {
            i++;
            j++;
        }
        else
            {
               if (s3[i] < s4[j]) i++
               else j++;
               count++;
            }
    }
    return count-1;
}

Actually, this idea is more or less the same as calculating the symmetric difference between two sets.

An Haskell solution by Alessandro Pezzato

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


parse :: String -> (String, String)
parse input = (a, b)
  where
    [a, b] = lines input

freq :: String -> [Int]
freq s = [length $ filter (== c) s | c <- ['a' .. 'z']]

solve :: String -> String -> Int
solve a b = sum $ abs <$> zipWith (-) (freq a) (freq b)

main = interact $ show . uncurry solve . parse

string frequency table