Problem: Making Anagrams

*Difficulty: Easy



Approach: To be able to make anagrams from two string, we have to find their common characters first. For example, if we have abccd and cdcc, then their common characters is c and d. Then we build two string contains only character that is in both string a and string b. In the previous example, string a = ccd and string b = cdcc. The last thing we need to do is make them anagrams. We do that by iterating through either string a or string b, with each character d, if there are more d in string a than string b, we remove d from a to make the number of d equal in both a and b. In our example, string b will remove 1 ‘c’, then a = ccd and b = dcc. Notice that we don’t have to do this on string, we rather do this on dictionary of string. Since the input only contains lower English alphabet, the maximum size of the dictionary will contain only 26 keys and 26 corresponding values. If key ‘c’ in a has higher value than key ‘c’ in b, then set its value to ‘c’ in b.

Implementation: Python 2.7

from collections import Counter

def make_anagrams(a, b):
    a_set = set(list(a))
    b_set = set(list(b))
    a_counter = Counter()
    b_counter = Counter()
    # get char in common 
    for c in a:
        if c in b_set:
            a_counter[c] += 1
    for c in b:
        if c in a_set:
            b_counter[c] += 1
    # make anagrams 
    for key in a_counter.keys():
        a_val = a_counter.get(key)
        b_val = b_counter.get(key)
        if a_val > b_val:
            a_counter[key] = b_val
            b_counter[key] = a_val
    # calculate removed char
    a_lost = len(a) - sum([a_counter.get(x) for x in a_counter.keys()])
    b_lost = len(b) - sum([b_counter.get(x) for x in b_counter.keys()])
    return a_lost + b_lost

if __name__ == '__main__':
    a = input().strip()
    b = input().strip()
    print(make_anagrams(a, b))