cool_shark My solution in c++.
int number_needed(string a, string b) { auto count = 0; vector<int> freq(26, 0); for (auto c : a) { ++freq[c - 'a']; } for (auto c : b) { --freq[c - 'a']; } for (auto val : freq) { count += abs(val); } return count; }
jonathen What does ++freq[c-'a'] and --freq[c-'a'] do?
ChrisDoesCode jonathen, freq is the vector created. It is declared a size of 26 values, all set to 0.
The first two (for) loops go through a string, char by char and use the freq vector to keep track of each char's occurrence.
++freq is increasing the value of the vector at the index [c minus 'a']. What you are seeing is ASCII interpretation for the index. Since 'a' is 97, if c was 'a', then the index would be [0] because 97-97. Same continues for 'b' which would be 98-97 indicating an index of [1].
cool_shark makes good use of one vector by using --freq to account for char matches between the two strings. Note that this is good programming practice instead of using nested loops which would have given a runtime of O(n^2) instead of its current linear runtime.
shash007 can you please explain me the last for loop ? in detail ?
cmag12 The last
forloop in this case is a newer feature in C++. This same type of loop is usually referred to as afor eachorfor inloop in other languages.I will explain this loop in a more pseudo-code way, and then explain it in C++ terms.
Say you have an array of elements. Instead of initializing an integer and then incrementing that integer and indexing into the array to get access to the element, it would be great if we could just have access to the elements themselves when we go through the array. If you had a row of kittens lined up and you wanted to pet them all, it'd be easy enough to say, "Give me the first kitten, please," then pet the first kitten, and then say, "Okay, give me the next kitten please." Notice how we don't care what index the next kitten is at, we just want the next kitten? Once we get to the end of the kitten row, we simply notice there's no more kittens left when we get the next one, and we quit petting the kittens.
Well in C++, we're use to iterating through arrays using indexes, instead of saying we just want the next element. But everything that I've just described above is very similar to what this last
forloop does.for (auto val : freq) { count += abs(val); }
If you don't know what the
autokeyword is, I suggest doing some quick reading on that. It shouldn't be too complicated.In this
forloop, what we end up doing is iterating through each element of the vectorfreq. In this case we make a copy of each element, and then use that within theforloop. If we wanted to use a reference to the element instead of copying it each time, we could instead say:for (auto &val: freq) {...Once we've gone through all the elements in
freq, we simply exit theforloop.for (auto &val : freq) { cou << "val=" << val << endl; }
If we had
vector<int>freq = {2,4,6}(this exact initialization is good for C++11 onward), then when we iterate through the loop, we would get:val=2 val=4 val=6
I hope this helps!
shash007 thank you cmag12
darshansharma_ [deleted]aayushis character
darshansharma_ Ok got it. Thanks
[deleted] [deleted]
hamadi_salahedd1 here's the code in C which would be very easy to understand.
#include <math.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <stdbool.h> int main(){ char* a = (char *)malloc(512000 * sizeof(char)); scanf("%s",a); char* b = (char *)malloc(512000 * sizeof(char)); scanf("%s",b); int charFrequency[26]= {0}; int i=0; while(a[i] != '\0') { charFrequency[a[i]-'a']++; i++; } i=0; while(b[i] != '\0') { charFrequency[b[i]-'a']--; i++; } int sum=0; for(int k=0; k<26; k++) { sum += (0<charFrequency[k])?charFrequency[k]:(-charFrequency[k]); } printf("%d", sum); return 0; }
MOHITSGNR Thanks hamadi
Steve_Pal please explain last for loop, in sample test case the charFrequency array first five elements value are greater than 0, so it add all value then how become answer is 4 ?
HarshKhetrapal can you please explain me the working of the while loop.
15B81A1222 I understood the program but how did the approach got to you it was amazing
jjwcvca I concur. This was a very insightful solution.
I did it in O(nlog(n)) time (because I sorted the two arrays first). I'm surprised none of the test cases timed out. :-)
Rsp721 thanks bro
akashmondal1810 I cann't figure out what am I doing wrong
int makeAnagram(string a, string b) { map mp;
int n = a.size(), m = b.size(); for(int i=0; i<n; i++){ if(mp.count(a[i])) mp[a[i]]++; else mp[a[i]] =1; } for(int i=0; i<m; i++){ if(mp.count(b[i])) mp[b[i]]--; else { mp[b[i]] =1; } } map<char, int>:: iterator it; int cot = 0; for(it=mp.begin(); it!=mp.end(); ++it){ cot+= (0<it->second)?it->second:(-it->second); } return cot;}
peterchaula Clever solution. Similar to mine except I used a map for the character frequencies.
--freq[c - 'a']can also be replaced by--freq[c % 'a']
Namrata1011 This is the first time that I came across to this 'auto' datatype. Can you give a brief info on it's use? (as compared to other datatypes)
cmag12 autois a feature new in C++11 onward. It allows the type of the variable to be inferred from its initilizer statement. For example:int i = 3; auto j = i; auto k = 10;
Instead of specifying
intforjandk, you can useauto, and the compiler will try to infer the type thatjandkshould be.It's especially useful when using iterators, as they can be quite long type specificers such as
vector<string>::iterator. It's also useful when code changes and if the code was previously usingautothen less has to be modified to be updated.
jil096 What if a and b are the same string, like 'cd' and 'cd'? In that way, it will return 0 but they are not anagrams.
dm1122 I agree. The promblem has wrong description. Solutions is not about anagrams, but about the same set of characters.
nullset2 I understand that it's not quite an anagram per-se, however you could argue that theoretically every string is an anagram of itself, so I think it holds up.
It's a nice problem anyway.
PremRanjanDev I would say description is RIGHT. We have to find out how many DELETION operation is required. In case of 'cd' and 'cd' we do not required any deletion operation as only shifting of characters of any string will make them anagrams hence result is 0. Thanks!
TioTala Simply elegant! Thanks!
clinton_stamper Here is my java solution for this
import java.util.Scanner; public class Solution { public static int numberNeeded(String first, String second) { int[] lettercounts = new int[26]; for(char c : first.toCharArray()){ lettercounts[c-'a']++; } for(char c : second.toCharArray()){ lettercounts[c-'a']--; } int result = 0; for(int i : lettercounts){ result += Math.abs(i); } return result; } public static void main(String[] args) { Scanner in = new Scanner(System.in); String a = in.next(); String b = in.next(); System.out.println(numberNeeded(a, b)); } }
namayogesh59 [deleted]yogesh_arora simply awesome
gustavo_gois My comment is the same: "simply awesome" rssss
aayushis can you please explain the enhanced for loops that you have used.I don't understand the format of lettercounts that you have used.
John_Tran For each character c in first.toCharArray()
So basically, it's looping through every char in first.toCharArray()
milosmns I don't think this is the part he was not understanding. He was probably referring to the char -> int Java conversion. Also shouldn't we be helping people in solving these problems? The question has negative score, not sure why is that.
alphasovereign Excellent!
maarichimitra Excellent
moconno1551 What is happening in the brackects under the first two for each loops?
kc_chaitanya89 He created an array with size 26, by default the value is 0 for all the indices of the array.
here, "lettercounts[c-'a']++";
let's assume char value of c = 'e'.
The ascii value of 'e' is 101
The ascii value of 'a' is 97
So, the above line of code becomes,
lettercounts[101-97]++;
==> lettercounts[4]++;
// the above code is equivalent to
// lettercounts[4] = lettercounts[4] + 1;
So, if you print lettercounts[4], it prints 1, and with subsequent iterations the count gets incremented.
try it out with a simple int array
mandalsambeet [deleted]
ssarans Its great to see how you've used Tries data structure approach in this one. I implemented this with HashMap, but that solution is not efficient becuase you have to maintain two hashmaps and compare the count of each character in both of them.
ssarans Question: Dont you think doing Math.abs on i will convert the negative value of i to positive and when you add it to the result its gonna add two positive value, which will ofcourse be incorrect? I think returning Math.abs(result) would be correct!
Kellenp If there is 1 value of "a" in the first string, and 2 values of "a" in the second string, you'd get -1. If there is a letter thats unpaired, you need to add it to the result whether its from the first or second string, hense the Math.abs.
Ex.
String: aaaab bbaaa
Array: [1, -1, 0, 0, 0, ...etc]
We need to remove 1 a and 1 b to make an anagram, so: Math.abs(1) + Math.abs(-1) == 2, which is the correct answer.
jenish9599 thanks
varunash7 I also implemented it with a hashmap but only used one.
My solution was very similar to clinton_stamper@ approach.
First I converted the longer string to a
HashMap<Character, Integer>
.
Then I iterated over the second string. In the for-loop, if the currentCharacter was in the map, then I decremented the value in the map by 1. When the value of a character reached 0, it meant that the longer string no longer had this character so I removed it from the map. For all characters that I came across without an entry in the map, I added 1 to the global differenceCount.
Then all I did was iterate over the entries left over in the map and add the values to the differenceCount.
Below is the code:
public class Solution { public static int numberNeeded(String first, String second) { Map<Character, Integer> mapOfCharacterCount; if (string1.length() >= string2.length()) { mapOfCharacterCount = getMapOfCharacterCount(string1); return getCharacterDifferenceBetweenStringAndMap(string2, mapOfCharacterCount); } else { mapOfCharacterCount = getMapOfCharacterCount(string2); return getCharacterDifferenceBetweenStringAndMap(string1, mapOfCharacterCount); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); String a = in.next(); String b = in.next(); System.out.println(numberNeeded(a, b)); } private static Map<Character, Integer> getMapOfCharacterCount(final String string) { final Map<Character, Integer> mapOfCharacterCount = new HashMap<Character, Integer>(); for (Integer currentIndex = 0; currentIndex < string.length(); currentIndex++) { Character currentCharacter = (Character) string.charAt(currentIndex); if (mapOfCharacterCount.containsKey(currentCharacter)) { Integer characterCount = mapOfCharacterCount.get(currentCharacter); mapOfCharacterCount.put(currentCharacter, ++characterCount); } else { mapOfCharacterCount.put(currentCharacter, 1); } } return mapOfCharacterCount; } private static int getCharacterDifferenceBetweenStringAndMap(final String string, final Map<Character, Integer> mapOfCharacterCountForSecondString) { int differenceCount = 0; for (int i = 0; i < string.length(); i++) { Character currentCharacter = string.charAt(i); if (mapOfCharacterCountForSecondString.containsKey(currentCharacter)) { Integer characterCount = mapOfCharacterCountForSecondString.get(currentCharacter); if ((characterCount - 1) == 0) { // The count for this character has reached 0 in the second string. Remove it from the map // so that if the character comes up again in the first string, we know to add to the // difference count. mapOfCharacterCountForSecondString.remove(currentCharacter); } else { mapOfCharacterCountForSecondString.put(currentCharacter, --characterCount); } } else { differenceCount++; } } for (Map.Entry<Character, Integer> entry : mapOfCharacterCountForSecondString.entrySet()) { differenceCount += entry.getValue(); } return differenceCount; } }
rohanraz91 public static int numberNeeded(String first, String second) { HashMap<Character, Integer> hm=new HashMap<>(); int count=0; for(int i=0;i<first.length();i++){ if(!hm.containsKey(first.charAt(i))){ hm.put(first.charAt(i), 1); }else{ hm.put(first.charAt(i),hm.get(first.charAt(i))+1); } } for(int i=0;i<second.length();i++){ if(!hm.containsKey(second.charAt(i))){ count++; }else{ hm.put(second.charAt(i),hm.get(second.charAt(i))-1); } } for(Entry<Character,Integer> entry:hm.entrySet()){ if(entry.getValue()!=0){ count+=Math.abs(entry.getValue()); } } return count; }
Have a look at this implementation of Map.
swethaReddy StringBuilder fsb = new StringBuilder(first.toLowerCase()); StringBuilder ssb = new StringBuilder(second.toLowerCase()); StringBuilder fsb1 = new StringBuilder(first.toLowerCase()); StringBuilder ssb1 = new StringBuilder(second.toLowerCase()); for(int i=0;i
fsb1.setCharAt(i, ' '); ssb1.setCharAt(j, ' '); break; } } } first= fsb1.toString().replaceAll("\\s+",""); second= ssb1.toString().replaceAll("\\s+",""); return first.length()+second.length();
swethaReddy [deleted]
ghophp that doesn't work.. doesnt even compile as I can see.. string1 is not defined.. second.. take the set string1 = A,B,C and string2 = X,X
sattujaiswal i did the same but this is awasome.. 2nd loop was good..
joaoh82 Thanks for this! Really nice solution! I converted to Go and it worked great. I was going into a completelly different direction.
sesharika Excellent!
ChinmayeePatra Too good
jigarsnaik Excellent Brillient !! What do you eat :D
lovan_artem Excellent work
Pikami Wow * _ *
wesleyrichmond So elegant you should wear a monocle
amitnanda4u Perfect!!!
priyanka_agarkar Excellent! its really simple and effective
lukeDevBE I like your solution. I also modified it slightly to use Java 8 IntStream for summing up the ints the functional way.
public static int numberNeeded(String first, String second) { int [] letters = new int[26]; for(char c : first.toCharArray()){ letters[c-'a']++; } for(char c : second.toCharArray()){ letters[c-'a']--; } return IntStream.of(letters).map( i -> Math.abs(i)).sum(); }
lukeDevBE What about even more Java 8 fun :D
public static int numberNeeded4(String one, String two){ int [] letters = new int[26]; one.chars().forEach( c -> { letters[c-'a']++; }); two.chars().forEach( c -> { letters[c-'a']--; }); return IntStream.of(letters).map( i -> Math.abs(i)).sum(); }
nitesh_dulal8 I have tried to understanding this solution using the explanation given in this page. But so far i have not understood it completly. Sorry a new bee here. can you please explain what is happening here letters[c-'a']++; and here letters[c-'a']--
bibik_julia Array
lettersis of length 26, and stores the "frequencies" of letters in the stringone. We index the array by the distance from the letter 'a'. So in letters['a'-'a']=letters[0] we will store the number of a's in stringone.
letters['b'-'a']=letters[1] the number of b's
letters['g'-'a']=letters[6] the number of g's and so on.
letters[c-'a']++ is a postfix notation and means the same as letters[c-'a']=letters[c-'a']+1, so we just encountered a letter and we add 1 to the corresponding slot.
Same with letters[c-'a']--, but this time we subtract all the frequencies in the stringtwo. This way, if there were 3 d's in stringoneand 5 d's in stringtwo, the 4th slot inletterswill be letters[3]=-2, but then we take care of it, by applyingMath.abs
ltocode I didn't get the return statement, sorry new to Java 8. Could you please explain?
return IntStream.of(letters).map( i -> Math.abs(i)).sum();
smile777 So elegant!
ltocode Great Solution Dude!!! Hats off
Geeky_98 beautiful...
pranavgupta93 superb logic...
agas3005 my code is passed.I couldnot think of using ascii.My code is:
import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*; import java.util.Arrays; public class Solution {
public static int numberNeeded(String first, String second) { int flength=first.length(); int slength=second.length(); //System.out.println("flength is"+flength); //System.out.println("slength is"+slength); char f[]=first.toCharArray(); char s[]=second.toCharArray(); int count=0; int fcount=0; int scount=0; int ans=0; if(flength>slength) { for(int i=0;i<flength;i++) { for(int j=0;j<slength;j++) { if(f[i]==s[j]) { s[j]=0; count++; break; } } } // System.out.println("if part"); ans=flength-count; } else if(flength<slength) { for(int i=0;i<flength;i++) { for(int j=0;j<slength;j++) { if(f[i]==s[j]) { s[j]=0; count++; break; } } } //System.out.println("elseif part"); ans=(flength+slength)-(2*count); } else { for(int i=0;i<flength;i++) { for(int j=0;j<slength;j++) { if(f[i]==s[j]) { count++; //f[i]=0; s[j]=0; break; } } } // System.out.println("else part"); ans=(flength-count)+(slength-count); } return ans; } public static void main(String[] args) { Scanner in = new Scanner(System.in); String a = in.next(); String b = in.next(); System.out.println(numberNeeded(a, b)); }} ....your solution is awesome.But what is the necessary of using ascii values.how can you think in this way?
swethaReddy [deleted]swethaReddy My solution in java using StringBuilder
StringBuilder fsb = new StringBuilder(first.toLowerCase()); StringBuilder ssb = new StringBuilder(second.toLowerCase()); StringBuilder fsb1 = new StringBuilder(first.toLowerCase()); StringBuilder ssb1 = new StringBuilder(second.toLowerCase());
for(int i=0;i<fsb.length();i++){ for(int j=0;j<ssb.length();j++){ if(fsb.charAt(i)==ssb1.charAt(j)){ fsb1.setCharAt(i, ' '); ssb1.setCharAt(j, ' '); break; } } } first= fsb1.toString().replaceAll("\\s+",""); second= ssb1.toString().replaceAll("\\s+",""); return first.length()+second.length();h953615104001 nicecode
mayank113463 Nice solution
ianchristner int number_needed(string a, string b) { int maxKept = 0; int answer = 0; vector<char> tempVecA(a.begin(), a.end()); vector<char> tempVecB(b.begin(), b.end()); int maxLose = (tempVecA.size()+tempVecB.size()); for(vector<char>::iterator iterA = tempVecA.begin(); iterA != tempVecA.end(); ++iterA){ for(vector<char>::iterator iterB = tempVecB.begin();iterB != tempVecB.end(); ++iterB){ if(*iterA == *iterB){ maxKept++; *iterB = 0; break; } } } answer = maxLose-2*maxKept; return answer; }
I solved mine the exact same way but using C++. I couldn't think of using ASCII either.
singh_shatendra How did your code pass the test.?It is producing incorrect result. Lets say string1="abccef" and string2="dgc";your code produces 5 as output and the ideal output should be 7.
agas3005 my code is passed.I couldnot think of using ascii.My code is:
import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*; import java.util.Arrays; public class Solution {
public static int numberNeeded(String first, String second) { int flength=first.length(); int slength=second.length(); //System.out.println("flength is"+flength); //System.out.println("slength is"+slength); char f[]=first.toCharArray(); char s[]=second.toCharArray(); int count=0; int fcount=0; int scount=0; int ans=0; if(flength>slength) { for(int i=0;i<flength;i++) { for(int j=0;j<slength;j++) { if(f[i]==s[j]) { s[j]=0; count++; break; } } } // System.out.println("if part"); ans=flength-count; } else if(flength<slength) { for(int i=0;i<flength;i++) { for(int j=0;j<slength;j++) { if(f[i]==s[j]) { s[j]=0; count++; break; } } } //System.out.println("elseif part"); ans=(flength+slength)-(2*count); } else { for(int i=0;i<flength;i++) { for(int j=0;j<slength;j++) { if(f[i]==s[j]) { count++; //f[i]=0; s[j]=0; break; } } } // System.out.println("else part"); ans=(flength-count)+(slength-count); } return ans; } public static void main(String[] args) { Scanner in = new Scanner(System.in); String a = in.next(); String b = in.next(); System.out.println(numberNeeded(a, b)); }} ....your solution is awesome.But what is the necessary of using ascii values.how can you think in this way?
swethaReddy StringBuilder fsb = new StringBuilder(first.toLowerCase()); StringBuilder ssb = new StringBuilder(second.toLowerCase()); StringBuilder fsb1 = new StringBuilder(first.toLowerCase()); StringBuilder ssb1 = new StringBuilder(second.toLowerCase());
for(int i=0;i<fsb.length();i++){ for(int j=0;j<ssb.length();j++){ if(fsb.charAt(i)==ssb1.charAt(j)){ fsb1.setCharAt(i, ' '); ssb1.setCharAt(j, ' '); break; } } } first= fsb1.toString().replaceAll("\\s+",""); second= ssb1.toString().replaceAll("\\s+",""); return first.length()+second.length();GEEKSHACKS0169 Nice solution
nikhil_vipparla [deleted]smita_panchaksh1 can you please telll significance of s[j]=0; stmt..?
tomly0221 great!
pukumath Done the same thing by using simle for loop instead of using enhanced for loop, but four test cases are not passed. What could be the reason.
codertoaster I came up with this horrible solution, though the logic is same as yours but I traverse the same string and arrays so many times which makes is horrible.
Thank for opening my eyes.
public static int numberNeeded(String first, String second) { String alpha="abcdefghijklmnopqrstuvwxyz"; int freq1[]=new int[26]; int freq2[]=new int[26]; for(int i=0;i<alpha.length();i++) { for(int j=0;j<first.length();j++) { if(alpha.charAt(i)==first.charAt(j)) ++freq1[i]; } } for(int i=0;i<alpha.length();i++) { for(int j=0;j<second.length();j++) { if(alpha.charAt(i)==second.charAt(j)) ++freq2[i]; } } int dels=0; for(int i=0;i<26;i++) { if(freq1[i]!=freq2[i]) dels+=Math.abs(freq1[i]-freq2[i]); } return dels; }
sarathbabu897 [deleted]
abhash24oct Donot use toCharArray() it takes O(n), so better use charAt(i): My Solution
int [] missingtracker = new int[26]; if(first.equals(second)) return 0; else{ for(int i=0;i<first.length();i++) missingtracker[first.charAt(i) - (int)'a']--; for(int j=0;j<second.length();j++) missingtracker[second.charAt(j)- (int)'a']++; int count=0; for (int i : missingtracker) { count+=Math.abs(i); } return count; }
mohamedahmedsaa1 Impressive :)
lin_jiachao This is the best solution i've seen so far. May I suggest shortening it even more by replacing
int result = 0; for(int i : lettercounts){ result += Math.abs(i); } return result;with
return Arrays.stream(missingtracker).map(x->Math.abs(x)).sum();Thanks for the awesome solution
dennnis_k Nice... perfect logic.
mykhailodorokhin it's faster to join two first loops into the one
Brhane_Abrham Excellent.
manmeet_singh Awesome !!!
ciandiarmuidgar1 Great solution, well done, I enjoyed it. Only improvement I can think of is to make first and second strings lowercase before any processing is done.
first = first.toLowerCase(); second = second.toLowerCase();
dilip_mudireddy Yes, in java to make it work we better need to convert.
int[] missingtracker = new int[26]; first=first.toLowerCase(); second=second.toLowerCase(); if (first.equals(second)) return 0; else { for (int i = 0; i < first.length(); i++) { missingtracker[first.charAt(i) - (int) 'a']--; } for (int j = 0; j < second.length(); j++) { missingtracker[second.charAt(j) - (int) 'a']++; } int count = 0; for (int i : missingtracker) { count += Math.abs(i); } return count; }
motyim wonderful solution
swethaReddy StringBuilder fsb = new StringBuilder(first.toLowerCase()); StringBuilder ssb = new StringBuilder(second.toLowerCase()); StringBuilder fsb1 = new StringBuilder(first.toLowerCase()); StringBuilder ssb1 = new StringBuilder(second.toLowerCase()); for(int i=0;i
fsb1.setCharAt(i, ' '); ssb1.setCharAt(j, ' '); break; } } } first= fsb1.toString().replaceAll("\\s+",""); second= ssb1.toString().replaceAll("\\s+",""); return first.length()+second.length();cseamangoyal please tell me how we can take char index
lettercounts[c-'a']
neeraj_vishwaka2 Salute Man
vishnu_maheswar1 This is genius!
hingoman25 Amazing solution
soumikd30 Nice... but if you don't mind could you explain why you left out 'a'
shareef_hiasat you should convert to lower case the both of strings. other wise A capital will be 65 and throws exception array out of bounds
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -32
brianmvance Constraints
It is guaranteed that and consist of lowercase English alphabetic letters (i.e., through ).
shareef_hiasat Sorry thanks did not notice that , you are right ))
kr0nd [deleted]anantmajhi16 Could you please explain this part: for(int i : lettercounts){ result += Math.abs(i); }
aSymptote_eh As a note, using toCharArray() is inefficient because it creates a copy of the string. Slightly faster to do a basic loop through the string:
for(int i=0; i<first.length(); i++){ lettercounts[first[i]-'a']++; }
nishchalpro1 beauty
maverick3727 can not get better!
omk7912 awesome
sandeepy excellent solution
dansarafa This is brilliant
noBody_00 Hi, I am new to lettercounts. Please help me to understand why do we use lettercounts[c-'a']++ for first string and lettercounts[c-'a']-- for second string?
Can we not use just one for both strings? What am I missing here?
woldegebrielkeb1 [deleted]sakshi_munya very nice ans...
Tan_007 I kept on thinking about dynamic programming. This one is much simpler.
Saras_Arya +1 for the explanation and approach. I did the same thing with 100 lines if code using one map and stuff but this trumps all. Even it was O(1) complexity. But this is way concise. Thanks
aannkkiitt Talking about space or time? U just said O(1)
swapnil_banga [deleted]swapnil_banga The 'not so elegant' version, if you are having trouble understanding this one:
int number_needed(string a, string b) { vector<int> freq(26, 0); int count=0; for(int i=0; i<a.length(); i++) { freq[a[i]-'a']+=1; } for(int i=0; i<b.length(); i++) { freq[b[i]-'a']-=1; } for(int i=0; i<26; i++) { count+=abs(freq[i]); } return count; }
svaldivi I haven't used vectors in this way before. I know it works, but I don't understand it. Why are you subtracting character 'a' in lines: freq[a[i]-'a']+=1; and freq[b[i]-'a']-=1;?
swapnil_banga Because our indexes run from 0-25 and not 97-122. Subtracting 'a' subtracts 97 from our ASCII code. For example, subtracting 'a' or 97 from the character a will result in an index of 0. It's upto you if you want to skip this, either way is fine.
svaldivi Okay that's helpful! Thanks :)
MIC0DE [deleted]MIC0DE [deleted]
trycatchnothing Ok, this works, but why does it only work when you loop through "a" first and then "b"?
Can't this be optimized to have one loop and increment/decrement based on the position of "a" and "b" at the same time?
aayushis See,if you are running both the loops simultaneosly,then there is a possibility that you might miss a few comparisons. The best way of doing this by keeping a pointer on one string and comparing it to the other string and when you are done with the comparison increment the pointer.
hitesh_sethiya I Implemented the same using HashMaps in Java. But then i came across this solution. Its nice. so implemented the same in java.
public static int numberNeededAr(String a,String b) { int[] af = new int[26]; int ops = 0; for(int i = 0; i < a.length(); ++i) af[a.charAt(i) - 'a']++; for(int i = 0; i < b.length(); ++i) af[b.charAt(i) - 'a']--; for (int anAf : af) ops += Math.abs(anAf); return ops; }
aayushis Can you please explain what you have done? Thanks!
hitesh_sethiya af(alphabetsFrequency) is the array created for 26 lower case letters from the english alphabets. It is declared a size of 26 values and by default all values are set to 0 in java. The first two (for) loops go through a string, char by char and use the af array to keep track of each char's occurrence. af[a.charAt(i) - 'a']++ is increasing the value of the array at the index [a.charAt(i) minus 'a'], Since 'a' is 97, if a.charAt(i) was 'a', then the index would be [0] because 97-97. Same continues for 'b' which would be 98-97 indicating an index of [1]. This implementation makes good use of one array by using af[b.charAt(i) - 'a']-- to account for char matches between the two strings. Note that this is good programming practice instead of using nested loops which would have given a runtime of O(n^2) instead of its current linear runtime. A similar explanation has been given by @ChrisDoesCode and the above explanation has been modified according to the code. This was actually implemented by @cool_shark, i merely converted it from C++ to java.
virendra_IAEA Super, thanks
agirdhar1987 great solution
ankeshk690 can u explain me how ur loop works
sanjeev_bhardwaj yess definitely ankesh
jenish9599 I don't understand the logic behind your code .. Please Explain me.
Thank you in advance
billbitt Nice solution. Here's my javacript implementation of your solution.
function main() { var a = readLine(); var b = readLine(); //console.log(a); //console.log(b); var alphabet=[]; // create an empty array for (var i = 0; i < 27; i++){ // fill it with 27 0's, each representaing a number in the alphabet alphabet.push(0); }; for (var i = 0; i < a.length; i++){ // increment alphabet array for all the letters in array 1 var alphaIndex = a.charCodeAt(i) - "a".charCodeAt(0); alphabet[alphaIndex] += 1; }; for (var i = 0; i < b.length; i++){ // decrement alphabet array for all the letters in array 2 var alphaIndex = b.charCodeAt(i) - "a".charCodeAt(0); alphabet[alphaIndex] -= 1; }; var tally = 0; // tally the results for (var i = 0; i < alphabet.length; i++){ tally += Math.abs(alphabet[i]); } console.log(tally); }
JohnnyHendrix Pretty cool solution. Here is the solution in python
from math import fabs def number_needed(a, b): letterArray = [0] * 26 for c in a: index = ord(c) - ord('a'); letterArray[index]+=1 for c in b: index = ord(c) - ord('a') letterArray[index]-=1 result = 0 for i in letterArray: result += fabs(i) return int(result) a = raw_input().strip() b = raw_input().strip() print number_needed(a, b)
AghalarovBahruz def number_needed(a, b): r=ca=cb=0 for i in set(a): ca=a.count(i) if i in b: cb=b.count(i) r+= abs(ca - cb) else: r +=ca for i in set(b): cb=b.count(i) if i not in a: r+= cb return r
olivier_cervello [deleted]
olivier_cervello [deleted]bibik_julia My Python solution:
def number_needed(a, b): count = 0 for i in range(97, 123): ia = sum(letter == chr(i) for letter in a) ib = sum(letter == chr(i) for letter in b) count += abs(ia-ib) return count
leny_yoann That is beautifull!
[deleted] but HOW?
lplj1948 Best Solution
mohammedabiyaz wow this is a pretty cool solution
h150030190 This is wonderful!
chukwudumiebi This solution was so good, i tried to modify it a bit:
def number_needed(a, b, alpha): count = 0 for i in alpha: freq_a = len(filter(lambda x:x==i, a)) freq_b = len(filter(lambda y:y==i, b)) count += abs(freq_a - freq_b) return count a = raw_input().strip() b = raw_input().strip() alpha = 'a b c d e f g h i j k l m n o p q r s t u v w x y z'.split(' ') print number_needed(a, b, alpha)
hualing_yu Great solution! Can use built-in fuction count:
def number_needed(a, b): count = 0 for i in range(97, 123): ia = a.count(chr(i)) ib = b.count(chr(i)) count += abs(ia-ib) return count
pawelbernaciak Slidely aranged to make it more pythonic:
from string import ascii_lowercase def number_needed(a, b): count = 0 for letter in ascii_lowercase: ia = a.count(letter) ib = b.count(letter) count += abs(ia - ib) return count
jrd24 can someone walk me through what is going on here? I don't understand what letter is
rjl2155 What is the role of the integers in the for loop
for i in range(97, 123):
for @bibik_julia 's solution?
Lord_yarik_93 are the letters in ascii 97=a, 98 = b,...,122 = z
moonatdeepak To check their character value by chr()
ghaderi_amin Absolutely amazing!!
angelopolotto In my solution, I tried make the function work for big inputs too, so, I sorted before test and I dicide use bisect to improove the list comprehension time:
import bisect # Complete the makeAnagram function below. def makeAnagram(a, b): a_s = sorted(a) b_s = sorted(b) if len(a_s) > len(b_s): a_s, b_s = b_s, a_s i = 0 while i < len(a_s): n_i = a_s[i] if n_i in b_s: j = bisect.bisect_left(b_s, n_i) del b_s[j] j = bisect.bisect_left(a_s, n_i) del a_s[j] i -= 1 i += 1 total = len(a_s) + len(b_s) return total
vasilij_kolomie1 The same, but for any language. #
from collections import Counter c_a = Counter(a) c_b = Counter(b) c_common = c_b & c_a return sum( c_a.values()) + sum( c_b.values()) - 2*sum(abs(i) for i in c_common.values())
hubrando Oh, this is a lot shorter than the way I did mine, but it is functionally the same.
elsporko I like your solution and altered it a bit using set operations so that it only considers the elements in a,b.
If other characters are introduced there will be no need to update the code and the loop only covers the elements present in both strings:
def makeAnagram(a, b): offset = 0 aset = set(a) bset = set(b) allset = set(aset | bset) for i in allset: ia = a.count(i) ib = b.count(i) offset += abs(ia-ib) return offset
hubrando This probably does pass the runtime complexity tests, but it's impossible to read. 97 to 123 represent the lowercase ascii character set in its decimal representation. I really don't get why you used sum here, so I can't really explain that.
jwilbs Simple solution:
def number_needed(a, b): a, b = list(a), list(b) a_vals = list(a) for i in a_vals: if i in b: a.remove(i) b.remove(i) return len(a) + len(b)
Intuition: Remove all shared elements, count what's leftover.
alejandro_m_ram1 It doesn't work, only pass 3 unit test.
anilgautam1987 simple & straight...
prasannakandreg1 replacing common alphabets in strings with null works!
def number_needed(a, b): for i in a: if i in b: b=b.replace(i,'',1) a=a.replace(i,'',1) return len(a)+len(b)
m86095 [deleted]jae_duk_seo Wow, this is super simple and straight.
NiranjanB Simple and clean. Best use of python.
hubrando .remove probably will make you fail the runtime complexity tests.
deqncho12345 why is a ufc fighter posting on hackerrank?
alejandro_m_ram1 Universal Fight Coder
Tommaso10 Nice solution, great idea! Here is the solution I found without using external libraries, and exploiting dictionaries instead:
def makeAnagram(a, b):
ma = {} mb = {} for i in range(len(a)): if a[i] not in ma.keys(): ma.setdefault(a[i],1) else: ma[a[i]]+=1 for i in range(len(b)): if b[i] not in mb.keys(): mb.setdefault(b[i],1) else: mb[b[i]]+=1 n = 0 for k in ma.keys(): if k not in mb.keys(): n += ma[k] else: if ma[k] != mb[k]: n += abs(ma[k] - mb[k]) for k in mb.keys(): if k not in ma.keys(): n += mb[k] return nmanojbiitm Why have you assigned letterarray =[0]*26. Can't we just leave it empty?
jacomatic pretty much did the same as you, but in python there's a built in counter for quick tallying.
famibica Impressive solution, congratulations!
joalfaru Can some one explain me, why are you writting the for loops like that, a dont understand the syntax.
cooldannyboy1984 I don't understand whay everyone said it works Does't your solution only make the same character count same? What if "abbc" and "abcb" To make them Anagram, the deletion count should be 2 not 0, right? "abbc" and "abcb" are not Anagrams.
alex205 I believe you misunderstood what an anagram is. abbc and abcb are in fact anagrams as they are the same length and include the same characters, just ordered differently.
alex205 Very nice and neat! Here is my C# implementation off the same algorythm.
using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void Main(String[] args) { // reading the two strings we need to evaulate string a = Console.ReadLine(); string b = Console.ReadLine(); // to work with the input strings we // convert them into arrays char[] string1 = a.ToCharArray(); char[] string2 = b.ToCharArray(); // set the final result counter to 0 // so we can use it at the end int result = 0; // Set a dictionary / hash table with which we // are going to track occurrencies of characters // in string1 and and string2 arrays // in C++, the equivalent of the dictionary below, // as cool_shark did, would look neater: // vector<int> freq(26, 0); // If perhaps someone has a niftier way o // implementing the data structure below, please, // let me know. Dictionary<char, int> frequencyDictionary = new Dictionary<char, int>() { {'a',0}, {'b',0}, {'c',0}, {'d',0}, {'e',0}, {'f',0}, {'g',0}, {'h',0}, {'i',0}, {'j',0}, {'k',0}, {'l',0}, {'m',0}, {'n',0}, {'o',0}, {'p',0}, {'q',0}, {'r',0}, {'s',0}, {'t',0}, {'u',0}, {'v',0}, {'w',0}, {'x',0}, {'y',0}, {'z',0} }; // go through the second string array and note // down the into the dictionary the number // of occurrence of each character by adding // 1 for each character for (int i = 0; i < string1.Length; i++) { char chr = string1[i]; frequencyDictionary[chr]++; } // go through the second string array and note down // the into the dictionary the number // of occurrence of each character by subtracting // 1 for each character for (int i = 0; i < string2.Length; i++) { char chr = string2[i]; frequencyDictionary[chr]--; } // At this point the dictionary should store numbers // we need to calculate our final result. // If for any key (our keys are // lowercase characters of the alphabet) // in the dictionary, the number is smaller or // greater than 0, // this means, that that is actually the character // that needs to be removed. // And it needs to ne removed (from either of // the original strings) // as many times as the absolute value of the number. // let us calculate the number of characters that we // need to remove from both // of the original strings. foreach(var pair in frequencyDictionary) { // if a character appears one or more times // in the second string // but it does not appear in the first string at // all, then the number // will be negative, thus we need to make it // absolute when we calculate // the final number result += Math.Abs(pair.Value); } Console.Write(result); } }
AlexMilligan It can be much simpler:
using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void Main(String[] args) { string a = Console.ReadLine(); string b = Console.ReadLine(); // elements automatically initialized to 0 int[] letterCounts = new int[26]; foreach (char c in a) { letterCounts[c - 'a']++; } foreach (char c in b) { letterCounts[c - 'a']--; } Console.WriteLine(letterCounts.Sum(x => Math.Abs(x))); } }
rodrigoramirez93 Could you please explain the lettersCount[ c - 'a'] part? Thaks
kaly_imsg He is using the ASCII value to set the value in the proper index. "a" ASCII value is 97, so if c is "b" (ASCII value = 98), the index would be "b"-"a" (98-97) = 1.
nikolay_em or, e.g. (disclaimer, this is the same implementation with sugar-syntax)
var table = new int[26]; a.ToList().ForEach(item => table[item - 'a']++); b.ToList().ForEach(item => table[item - 'a']--); return table.Sum(item => Math.Abs(item));
chigrinov_s_88 I have an even better solution for C#. Only two lines of code:
var dist = (a+b).Distinct();
return dist.Sum(y => Math.Abs(a.Count(x => x == y) - b.Count(x => x == y)));
hubrando Yeah but at this point the code starts to become unreadable.
[deleted] Or you could simply use map.
radharcode Solution assumes characters in english alphabet.
amrutamsunil Can u please, explain in detail what exactly ur code will do?
Thanks in advance,
karansaxena96 Can anyone please explain how the last for loop works and how it is calculating number of times char to be deleted from the two strings to make it anagrams?
aliTheGreat wow man this is very smart way of doing it. Thanks for sharing.
JulCesWhat So smart!!!
Amalpriya The code is really neat.... Superb
brianmvance Solution in python
def number_needed(a, b): ab_intersection = set(a).intersection(b) anagram = sum(min(a.count(char),b.count(char)) for char in ab_intersection) return(len(a)+len(b)-2*anagram) a = input().strip() b = input().strip() print(number_needed(a, b))
abdulshafy Explain please
brianmvance set(a).intersection(b) creates a list with a single occurance of the common characters between the two strings. Then iterate over each character of ab_intersection to determine the least number in either string. Summing the minimum occurance of common characters allows you to calculate how many characters to remove.
rahul_sharma20 [deleted]
machinekoder Ah, thats simpler than mine using Counter and sets, but the same idea I guess.
from collections import Counter # Complete the make_anagram function below. def make_anagram(a, b): c1 = Counter(a) s1 = set(c1) c2 = Counter(b) s2 = set(c2) for c, n in c1.items(): for i in range(n - 1): s1.add(c + str(i)) for c, n in c2.items(): for i in range(n - 1): s2.add(c + str(i)) common = s1.intersection(s2) rem1 = s1 - common rem2 = s2 - common return len(rem1) + len(rem2)
hubrando I still think the solution is more readable if you use Counters and dictionaries. However you don't need to have nested for loops. This problem can be done in O(n) run time.
rakshit9 what does -> for (auto c : a)
jvasquez I came up with the same solution using python but I used a dictionary instead saving unnecessary loops when adding the values
a = dict() s = raw_input().strip() for c in s: a[c] = a.get(c, 0) + 1 s = raw_input().strip() for c in s: a[c] = a.get(c, 0) - 1 r = 0 for c in a: r = r + abs(a[c]) print r
shivanshsharma81 Brilliant one
dat_bui I have same idea.
claine cool_shark, that is a beautiful solution. I had initially tried a similar (but exceedingly broken)thing using character arrays...
HOWEVER THIS BREAKS THE UNIT TESTS SO BEWARE!!! I'm just posting it here to help other people avoid my same mistake.
The reason it breaks is because of the size of the datasets. In this implementation, if an individual character occurs more than 128 times, the value stored at that character's position in the array will go from 127 to -128 and then go down from there, back to 0 and then back up again. You get a bunch of negative or otherwise incorrect values. A char is just not large enough to hold some of the counts that occur in the large data sets. Again, this is BROKEN, but I just wanted to share it FYI as a 'don't do it this way' sort of thing.
int number_needed(char * a, char * b) { char countA[MAX] = {0}; char countB[MAX] = {0};
for(int i = 0; i < strlen(a); ++i) { char charAtIndex = a[i]; countA[charAtIndex]++; } for(int i = 0; i < strlen(b); ++i) { char charAtIndex = b[i]; countB[charAtIndex]++; } int g = 0; for(int i = 0; i < MAX; ++i){ int diff = countA[i] - countB[i]; if (diff != 0) g = g + abs(diff); } return g;}
fernando_luz Why you didn't use a hashtable? I believe it's better to lookup.
karthiksagarmv exactly there is no need for keeping two counters :)
zikuth Awesome code, thanks!!
raof01 Wow! nice!
asterdan712 Dude thats some beautifully written code that really shows the power of modern C++ coding. Please advice on where you learnt it from. :)
Moo25 javascript's array can add more elements dynamically by specifying any index
function makeAnagram(a, b) { let vector = [] for(let element of a) { let index = element.charCodeAt(0) - 97 vector[index] = vector[index] || 0 vector[index] += 1; } for(let element of b){ let index = element.charCodeAt(0) - 97 vector[index] = vector[index] || 0 vector[index] -=1 } return vector.reduce((a,b) => Math.abs(a) + Math.abs(b)) }
Moo25 [deleted]vvipin_be16 Please describe how these loop will run??? This syntax of for loop is new to me.
tim_erwin brilliant lol
tim_erwin [deleted]tim_erwin [deleted]tim_erwin Javascript
function number_needed(a, b) { let count = 0; let freq = new Array(26).fill(0); const inc = (c, i) => freq[c.charCodeAt(0) - 'a'.charCodeAt(0)] += i; for (let c of a) inc(c, 1); for (let c of b) inc(c, -1); for (let v of freq) count += Math.abs(v); return count; }
alvaro_santiest1 Similar approach using accumulate with a lambda instead
int makeAnagram(string a, string b) { vector<int>v(26,0); for(auto& c : a){ v[c -'a']++; } for(auto& c : b){ v[c -'a']--; } return accumulate(v.begin(), v.end(), 0, [](int x, int y) { return abs(x) + abs(y);}); }
danieldai And the Python version:
from collections import Counter
def makeAnagram(a, b): c1 = Counter(a) c2 = Counter(b) return sum(((c1-c2)+(c2-c1)).values())
kashif_akram Simply genius, hats off for you.
alexseceleanu Very clean approach.
jdgzmn24 What's the equivalent of converting
for (auto c : a) { ++freq[c - 'a']; } for (auto c : b) { --freq[c - 'a']; } for (auto val : freq) { count += abs(val); }to a regular for loop? (e.g. for (int i = 0; i < a.size(); i++))
adammoses Well done. Must be shortest C++ for sure.
craig53 I just did this and then checked the discussion to find this which is almost character for character the same as my code. The only functional difference was I wrote freq(26) instead of freq(26, 0) since 0 is the default initializer anyway, therefore not needed in the constructor. Upvoted of course.
nscharichspam Wow, amazing
erithion Solution that does not need the third loop
int makeAnagram(string a, string b) { array<int, 256> hash{0}; int remove = 0; for (auto c: a) ++hash[c], ++remove; for (auto c: b) if (hash[c] > 0) --remove, --hash[c]; else ++remove; return remove; }
csk111165 Best Explanation Ever!
sven_petroll It appears to me my python solution is much better then the one posted in editorial:
from collections import Counter def number_needed(a, b): ct_a = Counter(a) ct_b = Counter(b) ct_a.subtract(ct_b) return sum(abs(i) for i in ct_a.values())
Cons?
pocomaxa None? Using one array for counts is a good optimization.
svens_ I like this approach.
Note that there's a difference between calling
.subtractand using the minus operator. The latter only returns positive results, which is unwanted in this case.
balda In the same spirit here is my Java 8 solution for the lulz:
public static int numberNeeded(String first, String second) { int[] freq = new int[26]; first.chars().forEach((c) -> { freq[c - 97]++; }); second.chars().forEach((c) -> { freq[c - 97]--; }); return Arrays.stream(freq).map(Math::abs).sum(); }
pocomaxa .map(Math::abs).sum()?
balda Applies the absolute value function to each element of the original stream and returns the resulting IntStream, from there we just aggregate the sum.
pocomaxa Yep, I was just pointing out that using function call 'Math::abs' instad of '(x) -> Math.abs(x)' was shorter.
balda ah yeah, i realized that and edited out the unnecessary casts and the abs function really quick, thxs for the feedback :)
pocomaxa Ah, the sugar! Let's go deeper, shall we? :)
public static int numberNeeded(String first, String second) { int[] freq = new int[26]; first.chars().forEach(c -> freq[c - 'a']++); second.chars().forEach(c -> freq[c - 'a']--); return Arrays.stream(freq).map(Math::abs).sum(); }
balda Ha, yeah! 'a' makes it much more readable. The solution is starting to look like python now :D
zandegran Looks great guys. Can you explain why substituting the last line with
return (int)Arrays.stream(freq).filter(f-> f!=0).count();
is not working for most of the test cases?
balda Hi, your statement is counting the number of unique chars that are in excess between the first and second strings. For this problem you need to count the total number of chars that are in excess, hence:
return Arrays.stream(freq).map(Math::abs).sum();
zandegran Understood. Thanks. This means that f!=0 is not taking in to account, if f is 2 or 3 or whatever, which it should.
unzain Darn... Java is really giving a good taste of functional programming. Very nice.
tao_zhang Java 7 version:
public static int numberNeeded(String first, String second) { int count = 0; int[] freq = new int[26]; for (char c : first.toCharArray()) freq[c - 'a']++; for (char c : second.toCharArray()) freq[c - 'a']--; for (int i : freq) count += Math.abs(i); return count; }
blainevanderson Why do you do freq[c - 'a']? Why do you subtract the lowercase a?
tao_zhang c - 'a'is the index of the array, which shold be an integer, so as you can see: if the char isathe index will be0, and if the char isbthen the index will be1, and so onPS:
- 'a'is equivalent of- 97according to ASCII table, except that it has a clearer expression of intention.
[deleted] How this works? Couldn't understand.
WittyNotes Many thanks for this! My java implementation ended up feeling really clunky, and I like seeing this tighter, more elegant approach.
collantescesar I'd use sum(map(abs,ct_a.values())) as result
rcbpeixoto That's amazing @sven_petroll, I think I did something similar manually, without the Counter thing
# a = abbaa # b = aacdabz # a2 = cdb # b2 = dab def set_to_dict(m_set, m_str): m_dict = {} for c in m_set: m_dict[c]=m_str.count(c) return m_dict def compare_dict(m_dict1, m_dict2): compare_sum = 0 for key,value in m_dict1.items(): if key in m_dict2: compare_sum += abs(value - m_dict2[key]) del(m_dict2[key]) else: compare_sum += value return compare_sum def number_needed(a, b): set_a, set_b = set(a), set(b) dict_a = set_to_dict(set_a, a) dict_b = set_to_dict(set_b, b) m_sum = compare_dict(dict_b, dict_a) m_sum += compare_dict(dict_a, dict_b) return m_sum a = input().strip() b = input().strip() print(number_needed(a, b))
raider64x [deleted]raider64x [deleted]raider64x My Solution
import string def number_needed(a,b): count = 0 my_dict = dict.fromkeys(string.ascii_lowercase, []) for c in string.ascii_lowercase: if c in a and c in b: my_dict[c] = [a.count(c),b.count(c)] elif c in a and c not in b: my_dict[c] = [a.count(c), 0] else: my_dict[c] = [0, b.count(c)] for c in string.ascii_lowercase: count += abs(my_dict[c][1] - my_dict[c][0]) return count
abhinavwalia95 I've got an idea from your code, and made it more pythonic. Have a look at Making Anagrams Challenge Solution in Python 3
makememad [deleted]
sayanarijit def number_needed(a, b): delete = 0 chars = set(list(a) + list(b))
for c in chars: delete += abs(list(a).count(c) - list(b).count(c)) return delete
neo1691 I started my solution with Counter in mind, however started using the concepts of keys for the counter combined with sets to get a set difference, and steered into fairly complicated direction.
Looking at your code, I now realize that Counter was indeed a better solution for this problem in python.
Lesson learned: Always go and check what more features are provided in the standard library (like counter) before moving away from it.
Thanks.
sawyer_gabriel Maybe a way of keeping it this efficient without the import? More of a question than anything else, and definitely not being a douche by insinuating I know a better way, because I don't haha.
cszchung You can avoid using Counter and save space by only using one dictionary (space is len(set(a + b)) rather than len(a) + len(b)). My solution:
def number_needed(a, b): anagram_dict = dict.fromkeys(a + b, 0) for letter in a: anagram_dict[letter] += 1 for letter in b: anagram_dict[letter] -= 1 return sum([abs(val) for val in anagram_dict.values()])
tony16 Really nice solution. Simplest one I've seen.
eperry4750 [deleted]eperry4750 [deleted]eperry4750 [deleted]eperry4750 def number_needed(a, b): dic = {} for word, value in [(a, 1), (b, -1)]: for letter in word: dic[letter] = dic.setdefault(letter, 0) + (value) return sum([abs(value) for value in dic.values()])
sayanarijit def number_needed(a, b): delete = 0 chars = set(list(a) + list(b))
for c in chars: delete += abs(list(a).count(c) - list(b).count(c)) return delete
sayanarijit def number_needed(a, b): delete = 0 chars = set(list(a) + list(b))
for c in chars: delete += abs(list(a).count(c) - list(b).count(c)) return deletesvdubl this is elegant solution. thank you
brianmvance Dictionary not used.
def number_needed(a, b): ab_intersection = set(a).intersection(b) anagram = sum(min(a.count(char),b.count(char)) for char in ab_intersection) return(len(a)+len(b)-2*anagram) a = input().strip() b = input().strip() print(number_needed(a, b))
imsandysaha1 why min() is used?
jarturomora simply beautiful, I didn't know the Counter container, definetely there is always something new to learn.
alesasnouski from collections import Counter def number_needed(a, b): ca = Counter(a) cb = Counter(b) d1 = cb - ca d2 = ca - cb return sum(d1.values()) + sum(d2.values())
KiemNguyen Beautiful
ryanlough subtracttakes any iterable, so you can just do:from collections import Counter def number_needed(a, b): ct = Counter(a) ct.subtract(b) return sum(abs(i) for i in ct.values())
Saves yourself from creating another Counter. Fantastic solution though!
olivier_cervello It seems like the following using dict is faster than Counter approach above.
Can someone confirm this ?
def number_needed(a, b): h = dict.fromkeys(a + b, 0) for c in a: h[c] += 1 for c in b: h[c] -= 1 return sum(abs(v) for v in h.values())
morita657 My answer is from same idea using Counter
from collections import Counter def number_needed(a, b): a = Counter(list(a)) b = Counter(list(b)) return len(list((a-b).elements())) + len(list((b-a).elements()))
iomumtaz Google didn't let me use Counter in their coding challenges, just a heads up.
dillingerjames Great solution; however, I think the point of most of these exercises are to manually program the functions. This is helpful though, and shows that there is already a perfect module for solving these sorts of problems.
avi_m_shapiro I basically had the same solution. I think using
mapis nice in thereturnstatement:return sum(map(abs, ct_a.values()))
raghuveer_s Tried it using the minus operator.
ac = Counter(a) bc = Counter(b) return sum((ac - bc).values()) + sum((bc-ac).values())
pouya_mn or even easier:
def makeAnagram(a, b): c=Counter(a) c.subtract(Counter(b)) return sum(map(abs,c.values()))
Counter.subtract does not remove negative values.
aiyaz_sarwar Ditto !!
andreweschaffer For Java there was an error in the given code. I needed to change the arguments for numberNeeded from (first, second) to (a, b).
SabriH Javascript Solution:
function main() { var a = readLine().split(""); var b = readLine().split(""); var countA = a.length; var countB = b.length; var count = countA + countB; var pair = 0; for(var i = 0; i < countA;i++){ for(var j = 0; j < countB; j++){ if(a[i] == b[j]){ b.splice(j,1); pair++; break; } } } console.log(count - (pair*2)); }
ajaycarnet My C# code: Same Logic Different Implementation.
static void Main(string[] args) { string a = Console.ReadLine(); string b = Console.ReadLine(); int LenA = a.Length; int LenB = b.Length; List<char> ListA = new List<char>(LenA); List<char> ListB = new List<char>(LenB); ListA = a.ToList(); ListB = b.ToList(); int total = LenA + LenB; int count = 0; for (int i = 0; i < LenA; i++) { if (ListB.Contains(ListA[i])) { count++; ListB.Remove(ListA[i]); } } Console.WriteLine(total - (2*count)); }Let me know if i can improve it. Thanks.
TWiStErRob Both of these solutions (JS and C#) are
O(n*m)wherenandmare the lengths of the inputs. You need to change to a different approach to reachO(n+m).Also (unrelated to the algorithm): you're created two
newlists that you throw away immediately.
Sort 1233 Discussions, By:
Please Login in order to post a comment