## 7 September 2014

### Quiz 21: Find number of deletions required to make 2 strings anagram

Problem:
Two strings are anagram if they have same character set. like abcde and deacb are anagram. Given 2 strings, you can delete characters from both to ensure that they become anagram. Find total number of deletions required.

Input Format:
String1 containing only lower case alphabets

String2 containing only lower case alphabets

Output Format:
total count of deletion required

Constraints:
none

Sample Input
aaabyz
aakkyb

Sample Output:
4

Explanations:-
Common characters are a,a,b,y. So a,z need to be deleted from string 1 and k,k need to be deleted by string 2. So total deletions are 2+2=4

Solution:

\$count = 0;
@arr3 = qw(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0);
@arr4 = qw(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0);

chomp(\$comp1=<STDIN>);
chomp(\$comp2=<STDIN>);

\$all = "abcdefghijklmnopqrstuvwxyz";
\$a1 = \$all.\$comp1;
@arr1 = split("",\$a1);
@arr1 = sort(@arr1);
\$a1 = join("",@arr1);
my \$tmp = 0;
for(my \$i=0;\$i<@arr1;\$i++)
{
if(\$arr1[\$i] eq \$arr1[\$i+1])
{
\$tmp++;
}
else{
push(@arr3,\$arr[\$i].\$tmp);
\$tmp = 0;
}
}
for(\$i=1;\$i<=26;\$i++)
{
shift(@arr3);
}

\$a2 = \$all.\$comp2;
@arr2 = split("",\$a2);
@arr2 = sort(@arr2);
\$a2 = join("",@arr2);
my \$tmp = 0;
for(my \$i=0;\$i<@arr2;\$i++)
{
if(\$arr2[\$i] eq \$arr2[\$i+1])
{
\$tmp++;
}
else{
push(@arr4,\$arr[\$i].\$tmp);
\$tmp = 0;
}
}
for(\$i=1;\$i<=26;\$i++)
{
shift(@arr4);
}

\$count=0;
for(\$j=0;\$j<26;\$j++)
{
if(\$arr3[\$j]>\$arr4[\$j])
{
\$count = \$count + \$arr3[\$j] - \$arr4[\$j];
}
elsif(\$arr3[\$j]<\$arr4[\$j])
{
\$count = \$count + \$arr4[\$j] - \$arr3[\$j];
}
}
print "\$count";

Tips:
Find occurrence of all alphabets a-z in both strings and then subtract them