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
Link
Complexity:
time complexity is O(N)
space complexity is O(N)
Execution:
Compare the frequency counts of the two parts.
Solution:
#!/usr/bin/py def buildMap(s): the_map = {} for char in s: if char not in the_map: the_map[char] = 1 else: 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] else: 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)
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.




