Determine if one string is a permutation of the another

Question

Can anyone give me some feedback if I'm using std::unordered_multimap optimally? I don't know the ins-and-outs of the std::unordered_multimap implementation.

I'm wondering if comparing two maps iterates through each of the elements in the map, making the algorithm \$O(N^2)\$ or if it just compares the hash of the map or something making the algorithm \$O(N)\$. Or would it just be better to use an array if I'm given this question in an interview?

bool is_permutation(const std::string& s1, const std::string& s2)
{
    assert(s1.size() && s2.size());

    if(s1.length() != s2.length())
        return false;

    std::unordered_multimap<int, char> m1, m2;

    for(int i = 0; i < s1.length(); ++i)
    {
        m1.insert({s1[i], s1[i]});
        m2.insert({s2[i], s2[i]});
    }

    if(m1 == m2)
        return true;

    return false;
}

Answer 1

Comparing two maps is linear, so that's not a big problem.

I don't think you've made particularly good use of maps though. As I see it, you have two choices. You could use an unordered_multiset, or you could use a unordered_map<char, size_t>. In the latter case, you'd keep a count of each character in the string, and increment the count for each character as you scan through the input strings.

Personally, I think it's generally simpler to just sort the two strings, then compare them:

bool is_permutation(std::string s1, std::string s2) {
    if (s1.length() != s2.length())
        return false;

    std::sort(s1.begin(), s1.end());
    std::sort(s2.begin(), s2.end());
    return s1 == s2;
}

A version making good use of an unordered_map:

bool is_perm2(std::string const &a, std::string const &b) { 
    std::unordered_map<char, std::size_t> s1;
    std::unordered_map<char, std::size_t> s2;

    if (a.length() != b.length())
        return false;

    for (unsigned char c : a)
        ++s1[c];
    for (unsigned char c : b)
        ++s2[c];
    return s1 == s2;
}

...will gain a substantial advantage if the strings involved are long. Don't expect miracles though--on typical strings (a few dozen to a few hundred characters) overhead often matters more than computational complexity, so this is unlikely to accomplish much. On the other hand, if you honestly expect to process strings of (say) a megabyte or more on a fairly regular basis, you can expect it to run significantly faster than the others.

I have not, however, gotten nearly as good of results from using a multiset or unordered_multiset. In fact, both are quite slow in my testing. I suspect the problem is that for this case, they're both storing a lot of data (a node for each character in the input), so before the string is large enough for computational complexity to matter much, they're overflowing the cache, so you end up with a lot of references to main memory. Note that when used as in the question, std::unordered_multimap ends up similarly (or probably even worse).

For anybody who might care, here's a chart of how various approaches work out for different sizes of strings:

[This shows the log of the time on the vertical axis, to help keep things visible across a wide range of sizes (and with them, times).]

So this shows the unordered_map having pretty high overhead, but nice, slow growth, so it's the slowest for small strings, but the fastest for strings over 8K in size.

Sorting is somewhat similar--faster for strings up to a kilobyte, but slower than the unordered_map for larger strings.

Using a raw array for the counts has behavior similar to sort, but even more dramatic--very fast for small strings, but slows down quite a lot for larger strings.

There seems to be no size at which the set/unordered_set (or unordered_multimap as used in the question) be the optimal choice.

Oh, for anybody who wonders about the odd stair-step look: I generated two tests for strings of each length: one with the strings identical, one with one character changed between them (i.e., one that should return true and another than should return false). I suppose if I wanted to be really complete, I should also add a test case for strings that are shuffled versions of each other, so they are unequal, but should still return true, but I haven't bothered with that (I have tested to be reasonably certain all the charted algorithms actually work though).

Edit 2:

After more testing, I have to agree with the consensus that counting characters in an array is a better choice:

bool is_perm3(std::string const &a, std::string const &b) { 
    std::array<std::size_t, std::numeric_limits<unsigned char>::max()+1> s1;
    std::array<std::size_t, std::numeric_limits<unsigned char>::max()+1> s2;

    if (a.length() != b.length())
        return false;

    for (unsigned char c : a)
        ++s1[c];
    for (unsigned char c : b)
        ++s2[c];
    for (std::size_t i=0; i<s1.size(); i++)
        if (s1[i] != s2[i])
            return false;
    return true;
}

I remain puzzled (and frankly, rather bothered) but the poor performance of std::vector vs. std::array in his test. We'd expect array to have less initial overhead, but the vector was pre-allocated, so speed differences after being set up should be quite minimal (but in this case definitely are not).

Answer 2

I would say yes, use an array.

Arrays afford very good memory locality, which is good for cache performance. They essentially are the most basic and efficient hash map if the key is the index.

You only need one array with 256 elements: first count up the number of times each character appears in the first string, and then count down for the number of times each character appears in the second string. Precisely if the two strings are permutations, the array will finish with all zeroes.

As a further hint at relative complexity, according to godbolt.org, your code produces 849 lines of assembly when compiled on the most recent GCC with -O3 optimisation. The following code produces 53 lines.

bool is_permutation(const std::string& s1, const std::string& s2)
{
    if(s1.length() != s2.length())
        return false;

    // There are usually 256 possible characters but on rare architectures may be more.
    constexpr possible_char_count = std::numeric_limits<unsigned char>::max()+1;
    std::array<size_t, possible_char_count > m1 = {}; // Zero initialized all places

    for(char c : s1) { // Count up for each character in the first string
        m1[static_cast<unsigned char>(c)]++; 
    }
    for(char c : s2) { // Count down for each character in the second string
        m1[static_cast<unsigned char>(c)]--; 
    }

    for (size_t t : m1) { 
        // If any character appears a net nonzero number of times,
        // the two strings are not anagrams.
        if (t != 0) { 
            return false;
        }
    }
    return true;
}

Lines of code are not, of themselves, a perfect indicator of what is the most efficient algorithm. After all, you can implement a nice short version of bubble sort! Nevertheless when the underlying approach is the same (that of counting characters) it is a fairly good indicator that one implementation is doing unnecessary work.

One reason to prefer a map to an array is that when the input strings are very short or very homogenous, then the map is likely to be more memory efficient. This may translate into speed improvements by avoiding allocation and inialisation overhead. As always, the only reliable way to decide is to profile with your real world inputs.

Answer 3

You have got the basics.
Though @Jerry Coffin points out some good points.

I would take this one step further.
A std::unordered_multimap is good for the general case. Where the thing you are finding and comparing can be arbitrarily complex. But here the thing we are comparing is a char. Very simple and a very small number of them (even if you use all 256).

So I would change to use an array of integers. One integer for each character. Though lets use a vector do easier comparisons.

// Stealing @Jerry Coffin code
bool is_perm2(std::string const &a, std::string const &b) { 

    if (a.length() != b.length())
        return false;

    std::array<int, 1 + UCHAR_MAX> s1;
    std::array<int, 1 + UCHAR_MAX> s2;

    for (unsigned char c : a)
        ++s1[c];
    for (unsigned char c : b)
        ++s2[c];
    return s1 == s2;
}

Notes:

• Complexity O(n).
• Overhead per iteration very small.
• Overhead high for initialization.