Problem: Making Anagrams

*Difficulty: Easy

Problem:

ctci-making-anagrams-english

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
        else:
            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))
Advertisements