HACKER RANK Algorithm Strings Challenges - Anagram Solution.'Py'

Algorithm Strings Challenges - Anagram Solution

Problem Statement

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.

Your task is to help him find the minimum number of characters of the first string he needs to change to enable him to make it an anagram of the second string.

Note: A word x is an anagram of another word y if we can produce y by rearranging the letters of x.

Input Format
The first line will contain an integer, T, representing the number of test cases. Each test case will contain a string having length len(S1)+len(S2), which will be concatenation of both the strings described above in the problem.The given string will contain only characters from a to z.

Output Format
An integer corresponding to each test case is printed in a different line, i.e. the number of changes required for each test case. Print −1 if it is not possible.

Constraints

• 1≤T≤100 
• 1≤len(S1)+len(S2)≤104

Sample Input

6
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

Sample Output

3
1
-1
2
0
1

Explanation
Test Case #01: We have to replace all three characters from the first string to make both of strings anagram. Here, S1 = "aaa" and S2 = "bbb". So the solution is to replace all character 'a' in string a with character 'b'.

Test Case #02: You have to replace 'a' with 'b', which will generate "bb".

Test Case #03: It is not possible for two strings of unequal length to be anagram for each other.

Test Case #04: We have to replace both the characters of first string ("mn") to make it anagram of other one.

Test Case #05: S1 and S2 are already anagram to each other.

Test Case #06: Here S1 = "xaxb" and S2 = "bbxx". He had to replace 'a' from S1 with 'b' so thatS1 = "xbxb" and we can rearrange its letter to "bbxx" in order to get S2.

Solution:

# Enter your code here. Read input from STDIN. Print output to STDOUT#!/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)

Thanks for Visiting, Hope this helps you....

Copyright © 2015 HackerRank.
All Rights Reserved