HackerRank 'Anagram' Solution

Martin Kysel · April 22, 2015

Short Problem Definition:
Sid is obsessed with reading short stories. Being a CS student, he is doing some interesting frequency analysis with the books. He chooses strings S1 and S2 in such a way that len(S1)−len(S2) ≤1



time complexity is O(N)

space complexity is O(N)


Compare the frequency counts of the two parts.



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(s):
    if len(s)%2 == 1:
        return -1
    mid = len(s)//2
    s1 = s[:mid]
    s2 = s[mid:]
    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])
    return diff_cnt

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        s = raw_input()
        print anagram(s)

Twitter, Facebook