HackerRank Anagram

Question

I was (yet again!) inspired by a previous question to post some code to solve the same problem. In this case, the problem in question is the Anagram challenge on HackerRank. The basic idea is that you're given some number of lines of input. Each line of input represents two strings (with no delimiter between them), each being as close to half the length of the line as possible (and if it's odd, the first is the shorter of the two, not that it matters much).

You're to find how many characters in the first need to be changed to make it an anagram of the second (or -1 if they can't be made anagrams of each other). For each line of input (other than the number specifying the length) you're to produce one line of output containing that number).

My code for this was as follows:

#include <iostream>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>

int anagram_check(std::string &line) {
    // If the length is odd, they can't be anagrams
    if (line.length() % 2 != 0) 
        return -1;

    size_t len = line.length() / 2;

    auto mid = line.begin() + len;

    // sort each half
    std::sort(line.begin(), mid);   
    std::sort(mid, line.end());

    // find number of characters that are different:
    std::string diffs;  
    std::set_difference(line.begin(), mid, mid, line.end(), std::back_inserter(diffs));
    return diffs.size();
}

int main() { 
    int num;

    // Read number of test cases:
    std::cin >> num;
    // Clear remainder of line from input buffer:
    std::string ignore;
    std::getline(std::cin, ignore);

    std::string line;
    for (int i = 0; i < num; i++) {
        std::getline(std::cin, line);
        std::cout << anagram_check(line) << "\n";
    }
}

Answer 1

Frankly, your solution is simple, short and elegant enough. I don't think there is much to add, but let's try a few tips an ideas:

• I sometimes advise people to arrange headers from a same library in alphabetical order; it generally helps to avoid including headers twice like you did with <iostream>. If you have a better semantic ordering for your headers, that's fine, but if you don't, alphabetical order helps to quickly find a header and avoid duplicate includes.

• It doesn't really matter, but using the global std::begin and std::end is slightly better in the event that you someday want to use a generic type instead of std::string.

• You only need the size of the set difference, not the set difference itself. If you wanted to, you could write a fancy iterator that only counts the number of times it is incremented and ignores what it is assigned to avoid copying things. That could be somewhat fun.

---

If you want a fun solution: associate every letter of the first word to the \$n\$th prime number (a to \$1\$, b to \$2\$, etc...) and multiply together every prime number correspond to the letters of the first word, let's call this result the product. Now, for every letter of the second word, associate it to its corresponding prime number p and compute std::div(product, p). If the remainder is \$0\$, it means that the letter was in the first word, assign the result of the division to product; otherwise, it means that the letter wasn't in the first word and you can increment the difference counter.

Of course it only works well with a small alphabet (you can cache the prime numbers if the size of the alphabet is small) and becomes impractical for big words unless you use infinite integers, but at least it's funny :p

Answer 2

The main thing that occurs to me as a problem here (and it may not be a real problem, but...) is what looks like inconsistency over the real goal: are we concerned primarily with making the code simple and maintainable, or with making it as fast as possible?

For example, the code currently defines a single string outside the loop (unnecessarily increasing its scope), apparently to avoid even the minimal overhead of defining a new string on each entry into the loop. It then passes this same string (by reference) to the character counting function, which (again, apparently trying to minimize overhead) proceeds to modify its input string.

In such a tiny program, that makes little difference, but it places substantial limits on the ability to reuse anagram_check under any other circumstances, and leads to much tighter coupling between anagram_check and whatever code calls it.

At the same time, as others have already noted, it uses std::sort and std::set_difference, even though they're rather...overkill for the task at hand. This takes a task that could be done with O(N) complexity, and unnecessarily increases the complexity to O(n log n). That's not a huge difference, especially for the expected inputs (unlikely to be extremely long), but nonetheless quite inconsistent with the previous almost fanatic devotion to minimizing overhead. Likewise, it it produces a set of results, even though it has no real need for the results themselves, only their size.

This could (possibly) make sense under a few circumstances, such as knowing that you're dealing with a huge number of strings, each of which is individually fairly short. In such a case, the time to sort each individual string becomes almost irrelevant, where the cumulative time to create a new std::string object for each iteration could be substantial (especially with an older library that doesn't include the short-string optimization, so every non-empty string that's created requires an allocation from the free store).

In general, however, it would probably be better to pass the input to anagram_check by value to make it able to work with input that can't be modified.

If you cared a lot about speed, you should probably just count the differences between the two input strings, rather than creating set of all the differences, then checking its size. Interestingly, the output is being created in an std::string, so a std::string is (somewhat unnecessarily) created every time anagram_check is called, despite passing its input by reference.

Answer 3

Due to the sorting, the time complexity of this is \$O(n \log n)\$. Which might be fine. It's a short and simple solution this way.

If time was more important than space, then you could build a map of character counts from the first half, and iterate over the second half, updating the counts as you go, and make a final pass to sum the absolute value of the counts to get the total differences. This would be \$O(n)\$, but at the cost of using extra space.