HackerRank ‘Make it Anagram’ Solution

Short Problem Definition:

Alice recently started learning about cryptography and found that anagrams are very useful. Two strings are anagrams of each other if they have same character set. For example strings"bacdc" and "dcbac" are anagrams, while strings "bacdc" and "dcbad" are not.

Alice decides on an encryption scheme involving 2 large strings where encryption is dependent on the minimum number of character deletions required to make the two strings anagrams. She need your help in finding out this number.

Given two strings (they can be of same or different length) help her in finding out the minimum number of character deletions required to make two strings anagrams. Any characters can be deleted from any of the strings.


Make it Anagram


time complexity is O(N)

space complexity is O(N)


Compare the frequency counts of the two parts.

The buildMap function can be replaced by:  from collections import Counter

def buildMap(s):
    the_map = {}
    for char in s:
        if char not in the_map:
            the_map[char] = 1
            the_map[char] +=1

    return the_map       

def anagram(s1, s2):
    map1 = buildMap(s1)
    map2 = buildMap(s2)

    diff_cnt = 0
    for key in map2.keys():
        if key not in map1:
            diff_cnt += map2[key]
            diff_cnt += max(0, map2[key]-map1[key])

    for key in map1.keys():
        if key not in map2:
            diff_cnt += map1[key]
            diff_cnt += max(0, map1[key]-map2[key])

    return diff_cnt

if __name__ == '__main__':
    s1 = raw_input()
    s2 = raw_input()
    print anagram(s1, s2)

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

  • plz try to explain what u did in each line

    • First I create a map of characters (line 14,15) . A = ‘abcda’ becomes {a = 2, b = 1, c =1, d =1} and B = ‘cdeff’ {c = 1, d = 1, e = 1, f = 2}. Then I go through all keys (abcd) in the A string and compare the map to the other map. (a is not in B so I count 2, b is not in B so I count 1, c is equal in both, d is equal in both -> the difference is 3). I do the same for the second map (giving me 1 e and 2 f). In total there are 6 differences.

      I do not use abs. I only count differences that are bigger than 0. That is because I want both compares to be symmetric. I could count an absolute difference in the first compare and skip it in the second.

      • NuuNoo Felicio

        I think there is one thing missing in your code because If the same char exists in the 2 strings but in differente quantities, your code will count that difference twice, one in the map2 loop and second in the map1 loop. Sugestion: in the first loop, remove the key from the map when it’s found:

        for key in map2.keys():
        if key not in map1:
        diff_cnt += map2[key]
        diff_cnt += max(0, map2[key]-map1[key]);

  • Aditya Jangid

    An easy and efficient way to above

    from collections import Counter
    a = Counter(raw_input())
    b = Counter(raw_input())
    c = a – b
    d = b – a
    e = c + d
    print len(list(e.elements()))