Given two strings, a and b, determine the minimum number of character deletions required to make a and b anagrams
I'm trying to figure out how my code could be improved. I solved a HackerRank problem from the Cracking the Coding Interview section, and am thinking that it should be able to be solved a simpler than what I did.


Probably. But these hacker problems are usually very specific. You can probably google a perfect solution in 10 minutes.


  What is a better, more efficient way of solving this problem?


Create a count of the number of each letter from both strings. To be anagrams these counts must be the same. So look across the counts and sum the differences.


  I am using C++, and since strings are immutable, 


No they are not. Strings are perfectly mutable.


  what I decided to do was to create two int arrays (vectors, actually) that hold the ASCII value of the chars in each string. Then I would sort the vectors. Then I would iterate through the arrays together, counting the number of elements that don't exist in the other.


The complexity of this is (ignoring the copy to a vector)

O(n1.log(n1))      // Sort first string
O(n2.log(n2))      // Sort second string
O(max(n1,n2))      // Loop Over counting.


That seems to work. I like getting the count of each letter better. The difference in the counts is the number of letters to be deleted. 

O(n1)             // Count each character into an array.
O(n2)             // Count each character into an array.
O(1)              // count the diffs.
                  // There is a loop over 255 characters (26 if you only count lower case letters).
                  // This is constant and not dependant on the size of
                  // the input and thus is `1`


Code Review.

Using Namespace

Please stop doing this.

using namespace std;


Its a bad habit that will cause you grief one day. See every other C++ code review for a good explanation.

Pass by const reference

You are passing the parameters by value. This will cause both the vectors to be copied.

int calcDeletions(vector&lt;int&gt; a, vector&lt;int&gt; b) {


Since you don't modify the values it can be made simpler by passing a const reference of each parameter. Thus having no copy.

int calcDeletions(vector&lt;int&gt; const&amp; a, vector&lt;int&gt; const&amp; b) {


Prefer Pre Increment

            deletions++;
            ai++;


Yes. Yes. It makes no difference for integers. But it does no harm to use pre-increment on integers either. But again it's one of those habits you should get into. There are situations where it does make a difference so it's best to pre-increment and then it will always be correct (even if you change the types of your objects).

Prefer operator[] over at()

The difference between the two is that at() performs bounds checking.

    for (int i = 0; i &lt; a.length(); i++) {
        aInt.push_back((int)a.at(i));
    }


In this context you are guaranteed that there is no out of bounds access as you are already checking that i is smaller than a.length(). Thus you are effectively doing the check twice.

Don't use C style casts.

C style casts are hard to spot.

 (int)a.at(i)
 ^^^^^


They are also extremely dangerous (they basically tell the compiler to shut up and do what you're told as I the programmer am god and know better than you the simple compiler). In reality this is usually wrong: the compiler always knows better than you and telling it to shut up is usually hiding an error message.

As a result, C++ has its own casts. There are actually four of them:

static_cast&lt;&gt;()
const_cast&lt;&gt;()
reinterpret_cast&lt;&gt;()
dynamic_cast&lt;&gt;()


Your above cast is actually best done by a static_cast&lt;&gt;()

static_cast&lt;int&gt;(a.at(i));


BUT There is no actual need to cast a char to an integer. This will happen automatically (as a char is an integer type the conversion is automatic) with no loss in precision.

Is there a need to put the largest first.

I don't see you taking advantage of this in the function above!

    // call calcDeletions function with the longer vector passed as first arg
    if (aInt.size() &gt; bInt.size()) {
        return calcDeletions(aInt, bInt);
    }
    else {
        return calcDeletions(bInt, aInt);
    }


Looking at the Cool Shark implementation you provided it still has a couple of issues.