ANASTR - Editorial

editorial
, ,
1

#PROBLEM LINK:

Practice
Contest

Author: Ayush Nagal

#DIFFICULTY:
MEDIUM

#PREREQUISITES:
String, Array.

#PROBLEM:
Given two strings a and b. We have to find the minimum number of characters to be deleted to make them anagarams.

#EXPLANATION:
Two strings are said to be anagrams if they have the same frequency of each character. As an example, strings abc and bac are anagrams, but abd and ash are not.
First of all, we need to find the frequency of each character in the strings a and b. It can be done using the following code:

int h1[26]={0},h2[26]={0};
int l1=a.length();
int l2=b.length();

for(int i=0;i<l1;i++)
h1[a[i]-'a']++;

for(int i=0;i<l2;i++)
h2[b[i]-'a']++;

Now we have the frequency array of both the strings. After this, we need to find the number of characters that differ in both the strings:

for(int i=0;i<26;i++)
{
    if(h1[i]==h2[i])
    continue;

    else if(h1[i]>h2[i])
    d+=(h1[i]-h2[i]);

    else
    d+=(h2[i]-h1[i]);

}

If the frequency of that particular character is same in both the strings, there is no need to delete any character. But if their frequency differs, then we need to delete those extra characters from one of them.

#AUTHOR’S SOLUTION:
Author’s solution can be found here.

3 Likes