Making Anagrams

I received a practice message from Hacker Rank. I like the idea to be reminded to spend some time practicing to solve a problem that is completely apart from the things I do at work or are in my learning schedule. The topic of the challenge is anagrams. You can find the description here.

After reading the description a couple times, it seems that the task is to remove characters from the two strings until we end up with two anagrams. In the example we end up with “a” as a string. Not much of an anagram. The goal is to return the number of characters removed from both strings.

I will use Java and the Eclipse IDE for the solution.

    // Complete the makingAnagrams function below.
    static int makingAnagrams(String s1, String s2) {

        int del = 0;
                
        // **** build hash map with counts of letters in s1 ****
        HashMap<Character, Integer> hm1 = new HashMap<Character, Integer>();
        for (char ch : s1.toCharArray()) {
            if (hm1.containsKey(ch)) {
                int count = hm1.get(ch);
                count++;
                hm1.put(ch, count);
            } else {
                hm1.put(ch, 1);
            }
        }

        // **** build hash map with counts of letters in s2 ****
        HashMap<Character, Integer> hm2 = new HashMap<Character, Integer>();
        for (char ch : s2.toCharArray()) {
            if (hm2.containsKey(ch)) {
                int count = hm2.get(ch);
                count++;
                hm2.put(ch, count);
            } else {
                hm2.put(ch, 1);
            }
        }
         
        // **** traverse hm1 looking at hm2 ****
        for (Map.Entry<Character, Integer> pair : hm1.entrySet()) {
            
            char ch1     = pair.getKey();
            int count1   = pair.getValue();
            
            // **** look for ch1 in hm2 ****
            if (hm2.containsKey(ch1)) {
                int count2 = hm2.get(ch1);
                del += Math.abs(count1 - count2);
            } else {
                del += count1;
            }
         }
        
        // **** traverse hm2 looking at hm1 ****
        for (Map.Entry<Character, Integer> pair : hm2.entrySet()) {
            
            char ch2     = pair.getKey();
            int count2   = pair.getValue();
            
            // **** look for ch2 in hm1 ****
            if (hm1.containsKey(ch2)) {
                int count1 = hm1.get(ch2);
            } else {
                del += count2;
            }
        }
        
        // **** ****
        return del;
    }

My idea was to create two hash maps, one per string. The hash maps would hold the characters and associated frequencies. Once that is done, iterate through the first map looking for each letter in the secondary hashmap while incrementing the count of characters to delete.

After that is done, repeat with the second hashmap taking into account which characters should be deleted. We should not double count deletions.

Submitted the code and passed all tests.

If you are interested in the complete solution which includes some tests (e.g., sort and display the strings) you can find it here.

As usual if you have comments or questions regarding this or any other post in this blog or if you wish me to address any issue that you might have regarding software development, please leave me a note below.

Keep on learning, practicing and enjoying developing code.

John

Please follow me on Twitter:  @john_canessa