Are strings anagram

Question

This is a question from the book "Cracking the Coding Interview".

Write a method to decide if two strings are anagrams or not

I think interviewer will not be convinced with this solution because here it is no test of logic. Please help me to optimise this solution.

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
std::string toLower(std::string str)
{
 std::transform(str.begin(), str.end(), str.begin(),
 [](unsigned char ch) { return std::tolower(ch); });
 return str;
}
bool areAnagrams(std::string& str1, std::string& str2)
{
 str1 = toLower(str1);
 str2 = toLower(str2);
 std::sort(str1.begin(), str1.end());
 std::sort(str2.begin(), str2.end());
 if (str1.compare(str2) == 0)
 {
 return true;
 }
 else
 {
 return false;
 }
}
int main()
{
 std::string str1, str2;
 std::cout << "Enter String 1: ";
 std::getline(std::cin, str1);
 std::cout << "Enter String 2: ";
 std::getline(std::cin, str2);
 bool res = areAnagrams(str1, str2);
 if (res == 1)
 {
 std::cout << "Strings are anagram\n";
 }
 else
 {
 std::cout << "Strings are not anagram\n";
 }
}

Answer 1

I think interviewer will not be convinced with this solution because here it is no test of logic.

I'm not sure what you mean by "because here it is no test of logic," but if what you mean is "because I found this puzzle too easy," then good! That's what the interviewer is likely to be hiring for: people who solve problems easily and quickly.

When you get an easy problem in an interview, that may be a sign that the interviewer is trying to judge your coding skills rather than your algorithmic/research skills. So make sure your code is as polished as (reasonably) possible.

• areAnagrams takes its parameters by non-const reference. This is probably a bug. The interviewer will ask you to "explain your choice." Your answer should be something like "oops, I forgot to remove the &." (This reflects a little badly on your coding skills.)

• if (res == 1) is a very strange way to test for boolean true-ness. It would be less unusual, but still a minor yellow flag, to test for if (res == true) or if (res). It would be good to remove the useless variable and test directly for if (areAnagrams(str1, str2)).

---

Similarly, in the body of areAnagrams, you have written

if (str1.compare(str2) == 0)
{
 return true;
}
else
{
 return false;
}

This is a very long-winded and confusing way of writing

return str1 == str2;

and is kind of a big deal. The interviewer is not looking to hire people who write eight lines of convoluted code when one line of simple code would do the job.

You also have an extra blank line at the beginning of areAnagrams; this shows a possible tendency toward sloppiness. The interviewer is not looking to hire people who might "typo" their way into a bug.

---

On the plus side, your definition of toLower is very good! The interviewer might ask you to explain why you took by value instead of by const&. The interviewer might ask you whether the line return str; makes a copy of the string or whether the copy is elided. (Trick question! The answer is "neither.")

• yuri: The answer is "neither." Why does NRVO not work in this case?
• Quuxplusone: Funny you should ask! NRVO works by constructing the object str directly into toLower's return slot. But in this case, toLower does not control where str gets constructed (because str is a parameter). The result is that str will be moved into the return slot — neither copied nor copy-elided, but moved.

Answer 2

I see some things that may help you improve your code.

bool is not int

The bool type is a full-fledged first class type in C++. If I were an interviewer reading this code, I'd be perplexed:

bool res = areAnagrams(str1, str2);
if (res == 1)
{
 std::cout << "Strings are anagram\n";
}
else
{
 std::cout << "Strings are not anagram\n";
}

A similar thing is being done here:

if (str1.compare(str2) == 0)
{
 return true;
}
else
{
 return false;
}

First, we are comparing a bool to 1 (an int) which is odd enough. Next, if we're returning the result of the comparison, why don't we return the result of the comparison?

return !str1.compare(str2);

Better still:

return str1 == str2;

Understand references

The prototype of the toLower function is this:

std::string toLower(std::string str);
bool areAnagrams(std::string& str1, std::string& str2);

So reading this, the toLower makes a copy of its argument and areAnagrams uses references. However, the first few lines of the latter function are these:

str1 = toLower(str1);
str2 = toLower(str2);

There's little point to making copies and then assigning the copy back to the original. What I would recommend instead is to have toLower take a reference and areAnagrams pass by value. That way, we have a much more logical interface in which toLower modifies the passed string but areAnagrams does not.

Use auto to simplify code

The better choice for res in main would be to declare it auto instead of explicitly naming bool.

Consider the use of locale

Rather than writing your own toLower, why not use the one in <locale>? Here's how that might look:

auto& facet{std::use_facet<std::ctype<char>>(std::locale())};
facet.tolower(&str1.front(), &str1.back());
facet.tolower(&str2.front(), &str2.back());

Use better naming

The function toLower is a good name because (with the suggested change mentioned above) it says what it actually does. However, res is not a good name and it's not necessary to have a separate variable anyway. Instead of this strange construction:

bool res = areAnagrams(str1, str2);
if (res == 1)
{
 std::cout << "Strings are anagram\n";
}
else
{
 std::cout << "Strings are not anagram\n";
}

I would probably instead have written this:

std::cout << "Strings " << (areAnagrams(str1, str2) ? "are" : "are not")
 << " anagrams\n";

Although, as @TobySpeight points out in a comment, better for the purposes of translating the string into another language would be to keep the strings intact. One way to do that:

std::cout << (areAnagrams(str1, str2) ? "Strings are anagrams\n"
 : "Strings are not anagrams\n");

Declare variables each on a separate line

Clarify variable declaration by declaring each one on a single line. See Guideline ES.10

Consider namespace or static

During an interview, I'd probably ask why you chose not to encapsulate the functions in a namespace, and why the functions are not static. There are arguments both ways for each of those; be aware of what they are and be able to explain and defend your choices.

• jamesdlin: std::string::compare returns <0, 0, or >0, so the first part of your answer doesn't make any sense.
• Edward: @jamesdlin: it was missing a ! which is now corrected.
• jamesdlin: I meant that the whole "bool is not int" premise is misdirected ("we are comparing a bool to 0..."; no, it's comparing int to 0). Regarding your edit: I personally dislike !str.compare(str) for the same reason as you originally give: bool is not int, and ! on an int seems weird.
• Edward: First, within main we have if (res == 1) which is comparing a bool to an int. Second, I agree that !str1.compare(str2) is not very good, which is why what I recommend instead is return str1 == str2; which I suspect we both agree is the most clear and straightforward way to do it.
• Toby Speight: Under "Use better naming", you go a bit further than I would. There's an argument against breaking strings into pieces like that - it's an anti-pattern that hinders translation. When your program is likely to be translated (and in an interview you do want to demonstrate that you can work with translators), it's usually better to keep strings whole - this is where C-style format strings can be valuable: std::printf(areAnagrams(str1, str2) ? "%s is an anagram of %s\n" : "%s is not an anagram of %s\n", str1.c_str(), str2.c_str());

Answer 3

You know, when deciding whether you have anagrams, you are generally only interested in alpha-numeric characters, the rest are disregarded.

Next, making extraneous copies is generally a bad idea. So, accept a constant view and don't make a copy.

When you accept a mutable reference, be sure that it's obvious from the function-name and arity that it's a mutable reference.

If you can, avoid external linkage. It promotes inlining and avoids unfortunate name-clashes.

Finally, a faster algorithm is normally preferable:

bool isAnagram(std::string_view a, std::string_view b) noexcept {
 unsigned counts[1ULL + (unsigned char)-1] = {};
 for (unsigned char c : a)
 ++counts[std::tolower(c)];
 for (unsigned char c : b)
 --counts[std::tolower(c)];
 for (std::size_t i = 0; i < std::size(counts); ++i)
 if (counts[i] && std::isalnum(i))
 return false;
 return true;
}

• Edward: While this may be a faster algorithm, is it a clearer algorithm? I think that for an interview, it may be better to write for clarity.
• Deduplicator: @Edward Yes, I would say so.
• user176443: (2) This code is different from OP's, it ignores non-alnum characters. (3) It's actually slower for short string, as it allocates an array of ~256 ints.
• Peter Cordes: Why int map[]? unsigned map[] will likely give the right answer in most cases for extremely long strings even if a bucket wraps around, without any signed-overflow UB. (If you can rule out long strings, unsigned char map[] cuts the cache footprint by 4 on most modern C++ implementations, and allows faster checking for non-zero buckets on targets where the compiler can use SIMD for the final loop.) I was going to say uint8_t, but you don't need to stop the code from working on implementations without uint8_t, like some DSPs where char is 32 bits.
• Peter Cordes: @user17... If you're checking all characters, then check if lengths are equal as an early-out before doing anything else. But allocating 1kiB on the stack is basically free; literally 1 instruction. Zeroing it has some small cost. Touching it might cause some cache misses, but store-forwarding might manage to hide a lot of the cost of that (i.e. the reloads don't have to wait for the stores to commit); only 32x 32-byte stores, so maybe 32 store-buffer entries for zeroing it. The load part of each increment should forward from the zeroing, but the store part uses another buffer.