Code Puzzle : Making Anagram problem

Problem statement: Calculate the minimum number of characters to be removed from any of the given two strings so that they become anagram.

Strategy: Store the frequency of occurrence of every characters (from a-z) of each of the strings in separate arrays, then the summation of difference in frequency of each character gives you the solution, abs(count1[str1[i]-‘a’] – count2[str2[i]-‘a’])

Here is the code,


#include <iostream>

using namespace std;

int min_remove_anagram(string a, string b) {
    int char_count_a[26]={0}, char_count_b[26]={0}, num_needed=0;
    // Count the frequencies of all characters in string a and b
    for(int i=0; i < a.size(); i++) {
        char_count_a[a[i] - 'a']++;
    }
    for(int i=0; i < b.size(); i++) {
        char_count_b[b[i] - 'a']++;
    }

    // The difference in the frequency count of all the characters is the solution.
    for(int i = 0; i < 26; i++) {        
       num_needed += abs(char_count_a[i] - char_count_b[i]);
    }
 return num_needed; 
}


int main()
{
    string str1 = "bcadeh", str2 = "hea";
    cout << min_remove_anagram(str1, str2);
    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s