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.

The problem is as follows:


  Strings: Making Anagrams
  
  Alice is taking a cryptography class and finding anagrams to be very
  useful. We consider two strings to be anagrams of each other if the
  first string's letters can be rearranged to form the second string. In
  other words, both strings must contain the same exact letters in the
  same exact frequency For example, bacdc and dcbac are anagrams,
  but bacdc and dcbad are not.
  
  Alice decides on an encryption scheme involving two large strings
  where encryption is dependent on the minimum number of character
  deletions required to make the two strings anagrams. Can you help her
  find this number?
  
  Given two strings, a and b, that may or may not be of the same
  length, determine the minimum number of character deletions required
  to make a and b anagrams. Any characters can be deleted from
  either of the strings. 
  
  Input Format
  
  The first line contains a single string, a. The second line contains
  a single string, b.
  
  Constraints
  
  
  \$1 \le |a|,|b| \le 10^4\$
  It is guaranteed that a and b consist of lowercase English alphabetic letters (i.e., a through z).
  
  
  Output Format
  
  Pring a single integer denoting the number of characters you must
  delete to make the two strings anagrams of each other.
  
  Sample Input

cde
abc

  
  Sample Output

4

  
  Explanation
  
  We delete the following characters from our two strings to turn them
  into anagrams of each other:
  
  
  Remove d and e from cde to get c.
  Remove a and b from abc to get c.
  
  
  We must delete 4 characters to make both strings anagrams, so we print
  4 on a new line.


My Implementation

I am using C++, and since strings are immutable, 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.

#include &lt;string&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt;

using namespace std;

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

    int deletions = 0;
    int ai = 0;
    int bi = 0;

    // step through arrays until the end of one is reached
    while (ai &lt; a.size() &amp;&amp; bi &lt; b.size()) {
        if (a[ai] &lt; b[bi]) {
            deletions++;
            ai++;
        }
        else if (a[ai] &gt; b[bi]) {
            deletions++;
            bi++;
        }
        else {
            ai++;
            bi++;
        }
    }

    // carry over left-overs
    deletions += (a.size() - ai);
    deletions += (b.size() - bi);

    return deletions;
}

int number_needed(string a, string b) {
    vector&lt;int&gt; aInt;
    vector&lt;int&gt; bInt;

    // create two int vectors to store ascii val of strings
    for (int i = 0; i &lt; a.length(); i++) {
        aInt.push_back((int)a.at(i));
    }
    for (int i = 0; i &lt; b.length(); i++) {
        bInt.push_back((int)b.at(i));
    }

    // sort vectors
    sort(aInt.begin(), aInt.end());
    sort(bInt.begin(), bInt.end());

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

int main() {
    string a;
    cin &gt;&gt; a;
    string b;
    cin &gt;&gt; b;

    cout &lt;&lt; number_needed(a, b) &lt;&lt; endl;
    return 0;
}


What is a better, more efficient way of solving this problem?
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.