CODEWITHSUNDEEP
c++stringalgorithmc++11
mbhatti_20
mbhatti_20

Reputation: 45

Counting minimum no. of char. to delete from two strings to make them anagrams

I have written following function to return no. of characters to delete from two strings to make them anagrams.

  int number_needed(string a, string b) {
  static int c;
  for(int i=0;i<=a.length();i++)    //loop over string a
      { char ch=a[i];
         int found=b.find(ch);
         if( found==string::npos)   //if character at a[i] not found in b
            {
              a.erase(i,1);          //delete character in a[i]
              c++;                   //inc. count c
            }
      }
  for(int i=0;i<=b.length();i++)       // repeat above looping for b string
      { char ch=b[i];
        int found=a.find(ch);
        if( found==std::string::npos)
           {
             b.erase(i,1);
             c++;
           }
      }
   return c;                           //finaly return no. of char. deleted
 }

I want to know if I have done everything right or not and whether my idea is fine in the context of problem. Also, can you make me understand the following code for the same problem which was given as solution.

 int number_needed(string a, string b) {
 auto count = 0;
 vector<int> freq(26, 0);
 for (auto c : a) { ++freq[c - 'a']; }
 for (auto c : b) { --freq[c - 'a']; }
 for (auto val : freq) { count += abs(val); }
 return count;
 }

Upvotes: 0

Views: 346

Answers (1)

kabanus
kabanus

Reputation: 25895

To answer your second part which is on topic:

 vector<int> freq(26, 0);

This vector will hold the amount of occurrences of a letter in the string.

for (auto c : a) { ++freq[c - 'a']; }

Go over the string letter by letter. If you're unfamiliar with the new for for syntax google it, basically it means foreach letter c in string a. The auto part tells the compiler to infer the type of the iterator from the thing your iterating - the string a in this case.

c-'a' converts the letter to an index. All letters appear consecutively in the ASCII char table (a mappings of char to int), so removing the first letter, 'a', will change it to an index between 0 and 26. Note this will work for lower case letters only: 'a'-'a'=0,'b'-'a=1 and so forth when converted to integer. Thus we are counting occurrences of letter in the string by adding 1 to the char vectors whenever we see it. 

for (auto c : b) { --freq[c - 'a']; }

Do the same on the second string, removing the frequencies this time. If a letter appears more times in a, freq of that letter will be positive with the exact excess, negative if it occurs more in b with the appropriate excess, or 0.

 for (auto val : freq) { count += abs(val); }

Sum up the excesses - absolute value handles the negative excess from b.

As TheGreatContini noticed, you don't maintain counts of duplicates.

Upvotes: 1

Related Questions