HackerRank – Making Anagrams

Overview

In this article we will see how to solve the Making Anagrams problem mentioned in Hacker rank.

A student is taking a cryptography class and has found anagrams to be very useful. Two strings are 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.

The student decides on an encryption scheme that involves two large strings. The encryption is dependent on the minimum number of character deletions required to make the two strings anagrams. Determine 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.

Example

a = ‘cde’ and b = ‘dcf’

Delete e from a and f from b so that the remaining strings are cd and dc which are anagrams. This takes 2 character deletions.

Code

First we will loop thought the character of the first string and will create a map with keys as the character and values as the number of occurrences of that character:

Map<Character, Integer> map1 = new HashMap(a.length());
for(char c : a.toCharArray()) {
    if (map1.containsKey(c)) {
        map1.put(c, map1.get(c) + 1);
    } else {
        map1.put(c, 1);
    }
}

Then we will do the same for the other string. After that we will map all the values of the first map with the second. If the key (character) doesn’t exists we will increment the count, if it exists but the values are not the same then we will add the difference to the count. We will also remove the item from the map.

int count = 0;
for (Map.Entry<Character, Integer> entry : map1.entrySet()) {
    if (map2.containsKey(entry.getKey())) {
        count += Math.abs(entry.getValue() - map2.get(entry.getKey()));
        map2.remove(entry.getKey());
    } else {
        count += entry.getValue();
    }
}

At the end we will add the remaining values to the count:

count += map2.values().stream().reduce(0, Integer::sum);

MakingAnagrams.java

import java.util.HashMap;
import java.util.Map;

public class MakingAnagrams {

    public static int makeAnagram(String a, String b) {
        Map<Character, Integer> map1 = new HashMap(a.length());
        for(char c : a.toCharArray()) {
            if (map1.containsKey(c)) {
                map1.put(c, map1.get(c) + 1);
            } else {
                map1.put(c, 1);
            }
        }

        Map<Character, Integer> map2 = new HashMap<>(a.length());
        for(char c : b.toCharArray()) {
            if (map2.containsKey(c)) {
                map2.put(c, map2.get(c) + 1);
            } else {
                map2.put(c, 1);
            }
        }

        int count = 0;
        for (Map.Entry<Character, Integer> entry : map1.entrySet()) {
            if (map2.containsKey(entry.getKey())) {
                count += Math.abs(entry.getValue() - map2.get(entry.getKey()));
                map2.remove(entry.getKey());
            } else {
                count += entry.getValue();
            }
        }

        count += map2.values().stream().reduce(0, Integer::sum);
        return count;
    }
}

Test

Below is a simple test for the above code:

import org.junit.Test;

import static org.junit.Assert.*;

public class MakingAnagramsTest {

    @Test
    public void makeAnagram() {
        assertEquals(2, MakingAnagrams.makeAnagram("cde", "dcf"));
        assertEquals(4, MakingAnagrams.makeAnagram("cde", "abc"));
        assertEquals(2, MakingAnagrams.makeAnagram("showman", "woman"));
        assertEquals(30, MakingAnagrams.makeAnagram("fcrxzwscanmligyxyvym", "jxwtrhvujlmrpdoqbisbwhmgpmeoke"));
    }
}

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: