Given two strings in lowercase, the task is to make them anagram. The only allowed operation is to remove a character from any string. Find minimum number of characters to be deleted to make both the strings anagram?
If two strings contains same data set in any order then strings are called Anagrams.
Examples:
Input : str1 = "bcadeh" str2 = "hea"
Output: 3
We need to remove b, c and d from str1.
Input : str1 = "cddgk" str2 = "gcd"
Output: 2
Input : str1 = "bca" str2 = "acb"
Output: 0
what if they cant be anagrammed?
>>59927704
print an error
I'm guessing some shit like:
start with all characters in str2 UNMARKED.
for 1 to n characters in str1,
check if str1[i] is in str2. that means it has to be in str2 and be UNMARKED.
if it is, mark it.
If it isn't, remove from str1 and add to the counter.
then do the exact same shit with str2 against str1 (what remains of str1, anyway.)
It is my dumb,stupid, lazy, simplest to think solution. Intelligent anons can probably find something better.
>>59927808
and of course, to mark the string you would have to make an auxiliary array of marks. Which isn't a problem since when you do the comparison, either str1 or str2 is static
def ang(a,b):
d = [0]*26
for c in a:
d[ord(c)-97] += 1
for c in b:
d[ord(c)-97] -= 1
return abs(sum(d)) if not min(d) < 0 < max(d) else -1
>>59927620if (op.isFaggot == true)
op.kys();
Homework posters should be banned.
This only works if the first string is the one that needs to be trimmed down, but still, it's a python one liner (minus the import for arguments lmao). Also it just prints the length of the first string if they can't anagram.import sys
print (len(sys.argv[1]) - len(set(sys.argv[1]).intersection(sys.argv[2])))
usage: python file.py str1 str2
>>59929045
Doesn't work on repeated letters.
>>59927831
Same thing in C++
I guess the most efficient way is to allocate an array of 26 ints, each representing the number of times the letter has been seen, -1 for string b, +1 for string a. The number of characters that need to be deleted is the addition of all the characters in string b not seen in a and vice versa.int minAnagram(std::string a, std::string b){
int c[26];
for (int i = 0; i < a.length(); ++i){
++c[a[i] - 'a'];
}
for (int i = 0; i < b.length(); ++i){
--c[b[i] - 'a'];
}
int min = 0, max = 0;
for (int i = 0; i < 26; ++i){
c[i] < 0 ? min += c[i] : max += c[i];
}
return std::abs(min) + max;
}
The real question is why they would ask me to do your homework on an interview?