ISourceCode

Make the frequent cases fast and the rare case correct

Find the minimum number of letters which must be removed from two words so that the remaining portions of the two words become anagram

Problem taken from here

Two words are said to be anagrams of each other if the letters from one word can be rearranged to form the other word. For example, occurs is an anagram of succor; however, dear is not an anagram of dared (because the d appears twice in dared, but only once in dear). The most famous anagram pair (in English) is dog and god.
The anagrammatic distance between any two words is the minimum number of letters which must be removed so that the remaining portions of the two words become anagrams. For example, given the words sleep and leap, we need to remove a minimum of three letters —two from sleep and one from leap —before what’s left are anagrams of each other (in each case, lep). With words such as dog and cat, where the two have absolutely no letters in common, the anagrammatic distance is an extreme (explicitly 6) since all the letters need to be removed. (Here, a word is always an anagram of itself.)
You must write a program to calculate the anagrammatic distance between any two given words.

Input
The first line of the input will contain a positive integer value N (less than 60,000) indicating the number of cases. Each case will consist of two words, possibly empty, each given on a single line (for a total of 2N additional lines).
Although they may have zero length, the words are simple —the letter are all lowercase and are taken from the usual twenty-six letter English alphabet (abcdefghijklmnopqrstuvwxyz). The longest word is pneumonoultramicroscopicsilicovolcanoconiosis.

Output
The output should consist of the case number and the anagrammatic distance, formatted as shown.

Sample Input

4
crocus
succor
dares
seared
empty

smell
lemon

Sample Output

Case #1: 0
Case #2: 1
Case #3: 5
Case #4: 4

import math
p = []
for i in range(0,26):
        p.append(0)
j = 0
s1 = raw_input("Enter the first string : ")
s2 = raw_input("Enter the second string : ")
for i in range(0,len(s1)):
        t=ord(s1[i])-ord('a')
        p[t] = p[t] + 1

for i in range(0,len(s2)):
        t=ord(s2[i])-ord('a')
        p[t] = p[t] - 1

cnt=0
for i in range(0,26):
        cnt =cnt + math.fabs(p[i])
print "The anagrammatic distance between the two given words are :",cnt

OUTPUT:

labuser@ubuntu:~$ python anagdist.py
Enter the first string : dares
Enter the second string : seared
The anagrammatic distance between the two given words are : 1.0
labuser@ubuntu:~$
labuser@ubuntu:~$
labuser@ubuntu:~$ python anagdist.py
Enter the first string : empty
Enter the second string :
The anagrammatic distance between the two given words are : 5.0
labuser@ubuntu:~$
labuser@ubuntu:~$
labuser@ubuntu:~$ python anagdist.py
Enter the first string : crocus
Enter the second string : succor
The anagrammatic distance between the two given words are : 0.0
labuser@ubuntu:~$
labuser@ubuntu:~$
labuser@ubuntu:~$ python anagdist.py
Enter the first string : smell
Enter the second string : lemon
The anagrammatic distance between the two given words are : 4.0
labuser@ubuntu:~$

I chose to write the program this way rather than the prescribed input

One response to “Find the minimum number of letters which must be removed from two words so that the remaining portions of the two words become anagram

  1. bartender February 13, 2013 at 10:53 am

    ” I chose to write the program this way rather than the prescribed input “.
    ———————————————————————————————————–
    The way you have coded this problem makes it easier to understand.Nice work.

    Two strings when transformed by minimum anagrammatic distance to an anagram can result in different length anagrams by different methods.

    example: sleep and leap —-> remove s,e and add a to ‘sleep’ to make it as ‘leap’. This way both strings will have length 4 ( length of string ‘leap’) and anagrammatic distance is 3 as we did 3 operations. (removing s,e and adding a = 2+1 i.e. 3 operations.)

    Another way would be to remove s,e, from ‘sleep’ (2 operations) and removing a from ‘leap’ (1 operation). This way both the strings will be transformed to ‘lep’ with length 3 (length of string ‘lep’)

    So, with the same anagrammatic distance we can get different length anagrams starting from two strings.Although this doesn’t matter in context of current problem but we can have a follow-up problem to give the largest length anagram based on minimum anagrammatic distance of 2 strings.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: