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
Rsp721 thanks bro
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
anirudh12n96 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!
anirudh12n96 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; }
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?
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!
cassar_samantha 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!!
imcclea1 could you possibly explain what your two sum calls are summing up? Are they summing up the asci table amounts or the number of times that letter == chr(i)
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())
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.
deqncho12345 why is a ufc fighter posting on hackerrank?
alejandro_m_ram1 Universal Fight Coder
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.
[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]
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.
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.
rajconnect1612 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))
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())
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.
caenietoba function main() { var a = readLine(); var b = readLine(); var arrayA = a.split( "" ); var arrayB = b.split( "" ); var numCoincidencia; var lengthA = arrayA.length; var lengthB = arrayB.length; if( lengthA > lengthB ) numCoincidencia = anagram( arrayB, a ); else numCoincidencia = anagram( arrayA, b ); console.log( (lengthA + lengthB - numCoincidencia - numCoincidencia) ); } function anagram( arrayShorter, stringLargest ){ var numCoincidencia = 0; var index; var charFounded; for( var i in arrayShorter ){ index = stringLargest.indexOf( arrayShorter[i] ); if( index != -1 ){ charFounded = stringLargest.charAt( index ); stringLargest = stringLargest.replace( charFounded, " " ); numCoincidencia++; } } return numCoincidencia; }
erdemtomus [deleted]
phinguyen712 Here is how I do it using hash map so that we dont have to deal with (n*m) checks.
a = a.toLowerCase().split('').sort(); b = b.toLowerCase().split('').sort(); var Maparray = function(testArr){ var object ={}; testArr.forEach(function(arrayItem){ if(arrayItem in object){ object[arrayItem] +=1; }else{ object[arrayItem] = 1; } }); return object; }; var aObject = Maparray(a); var bObject = Maparray(b); var matchCount = 0; for( var key in aObject){ if(key in bObject){ var matches = 0; if(aObject[key] === bObject[key]){ matches = 2 * aObject[key]; }else{ matches = (aObject[key] > bObject[key]) ? bObject[key]:aObject[key]; matches = matches * 2; } matchCount += matches; } } console.log(a.length + b.length - matchCount);
yousefmms public static int NumbersRequiredToDeleteFromBothStrings(string first, string second) { for (var i = 0; i < first.Length; i++) { var c = first[i]; int index = second.IndexOf(c); if (index >= 0) { second = second.Remove(index, 1); first = first.Remove(i, 1); i--; } } return first.Length + second.Length; }
kanchan0attri what does splice(j,1) do?
ajaycarnet Splice is used to remove elements from the array. here it starts removing elements from j. The nextone is for number of number of elements to be removed. here it's 1 element.
hope you understood. visit this for more. http://www.w3schools.com/jsref/jsref_splice.asp
david6p2 I solved similarly in Swift 3:
func readAndSearchForAnagrams(){ // Read Strings let fstString = readLine()! let sndString = readLine()! let caractersCount = charactersToDeleteToBeAnagrams(from: fstString, with: sndString) print(caractersCount) } func charactersToDeleteToBeAnagrams(from firstString:String, with secondString:String) -> Int { //Mutable copy of the second String var stringTwo = secondString var counter = 0 // Search if each character of first string exist in second String for index in firstString.characters.indices { if let indexInStringTwo = stringTwo.characters.index(of:firstString[index]) { // If exist, then increment the counter by 2(one per character in each string) counter += 2 // And remove it from second string stringTwo.remove(at:indexInStringTwo) } } // Concatenate them and return the amount of characters minus the counter of characters that exist on both. // That give us the numer of characters that doesn't exist on both let completeString = firstString + secondString return completeString.characters.count - counter } readAndSearchForAnagrams()
wasmithee Here's my JavaScript solution:
function countOfCharactersToRemove(str_1, str_2) { let freq = {}; str_1.split('').forEach((c) => {freq[c] = (freq[c] || 0) + 1}); str_2.split('').forEach((c) => {freq[c] = (freq[c] || 0) - 1}); return Object.keys(freq).map((key) => {return Math.abs(freq[key])}).reduce((a, c) => {return a + c}); }
caioertai Pretty interesting solution. Much faster than anything involving indexOf. Thanks for sharing it.
Thainan Thank you to the contribution. I just did some things to increase de legibility of it:
function countLesserAnagram(word1, word2) { var frequency = {}; word1.forEach(char => frequency[char] = (frequency[char] || 0) + 1); word2.forEach(char => frequency[char] = (frequency[char] || 0) - 1); return Object.keys(frequency).map(key => Math.abs(frequency[key])).reduce((a,b) => a + b); }
akimy I've the same, but I prefer using ES6 syntax. But your solution also fine. gj.
main = () => { const firstWord = readLine().split('') const secondWord = readLine().split('') let initialLettersCount = firstWord.length + secondWord.length firstWord.forEach((firstWordLetter) => { for (let j = 0; j < secondWord.length; j++) { if (firstWordLetter === secondWord[j]) { secondWord.splice(j, 1) initialLettersCount -=2 break } } }) console.log(initialLettersCount) }
yousefmms Aha, Thes same algorithm, but different tool/lang
O_Vargas_BOBG Thank you for this solution.. I had a very similar solution but it only passed three of the cases. After seeing break here, I added it to my code and it passed all the test cases.
eric_andrew_lew1 This works but the runtime of this solution is O(a * b) which is not great.
SarathKumar19 My solution is...
public class Solution { public static int numberNeeded(String first, String second) { Map<Character, Integer> count = new HashMap<>(); for( char ch: first.toCharArray() ) { int ct = count.containsKey(ch) ? count.get(ch) : 0; count.put(ch, (ct + 1)); } for( char ch: second.toCharArray() ) { int ct = count.containsKey(ch) ? count.get(ch) : 0; count.put(ch, (ct - 1)); } List<Integer> values = new ArrayList<>( count.values() ); int total = 0; for( Integer v: values ) { total += Math.abs(v); } return total; } 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)); } }
susmithamenda My solution is very similar to yours, but most of the test cases have failed. can you tell me why?
public static int numberNeeded(String first, String second) { int numberNeeded = 0; Map<Character, Integer> count = new HashMap<>(); for(char c : first.toCharArray()){ if(count.containsKey(c)) count.put(c, count.get(c)+1); else count.put(c, 1); } for(char c : second.toCharArray()){ if(count.containsKey(c)) count.put(c, count.get(c)-1); else count.put(c, 1); } for(int value: count.values()){ if(value != 0){ numberNeeded++; } } return numberNeeded; }acm_liu11 Hey susmithamenda,
The reason why it doesn’t work is because in:
for(int value: count.values()){ if(value != 0){ numberNeeded++; } }
You are not considering if the value > 1. You are just assuming that both strings are unique in characters. For instance, if value is “2” or “-2” - it is still being treated as only if value = 1 (numberNeeded++).
Secondly, another problem with this code is when the second string is iterating through the map. It is possible that you delete a previous entry that you have already done.
for(char c : second.toCharArray()){ if(count.containsKey(c)) count.put(c, count.get(c)-1); else count.put(c, 1); }
For example:
First: “d” Second: “ccc”
After adding it to map (first for loop): Map: <”d”, 1>
After the checking map in second for loop:
first iteration: Map: <”d”, 1> <"c", 1>
second iteration: (DELETED A PREVIOUS ENTRY HERE) Map: <”d”, 1> <"c", 0>
third iteration Map: <”d”, 1> <"c", -1>
Hope that helps, Cheers
susmithamenda Got it. Thanks for the help.
ndel314 Just change
count.put(c, 1);tocount.put(c, -1);in your second for loop. Then you just could sum the absolute values of both maps.
antrikshverma2 Hello ACM , Thanks for explanation
But im still not gettin your second point "Secondly, another problem with this code is when the second string is iterating through the map. It is possible that you delete a previous entry that you have already done."
Because during second loop while adding entry in map for character which already exist :
count.put(c, count.get(c)-1)
We are capturing previous value for that character[Key] and then subtracting it , So how we are getting affected even if it is creating new entry [Which hashmap is suppose to do if we try to add key which already exists].
Where im goin wrong .
acm_liu11 Hi Antrikshverma2,
That’s right – you have the right idea of what the hash table is supposed to do.
However, in susmithamenda’s example, he did:
for(char c : second.toCharArray()){ if(count.containsKey(c)) count.put(c, count.get(c)-1); else count.put(c, 1); }
It is possible that we get an example such as:
First string: “a” Second string: “b, b” Our desired answer would be 3.
However, if we use the second for loop above, our map would look like:
< a, 1 > , < b, 0 > We would get an answer of 1.
This is incorrect because he added count.put(c, 1).
When we see the first “b”, we add “b” into the map( < b, 1 >). On the second iteration, since “b” already exists as a key in the hash table, we delete the value by 1, which gives us 0.
As Ndel mentioned, the fix would be to change it into count.put(c, -1) and sum the absolute values.
Hope that helps, Cheers
SarathKumar19 Change this
if(value != 0){ numberNeeded++; }
to this
numberNeeded += Math.abs(value);
You are supposed to eliminate the common characters between 2 strings and sum up (not increment) absolute values of occurrences of other characters in both strings
For example, if A = "abe" and B = "aabc", resulting hashmap would be like this { 'a': -1, 'b': 0, 'c': 1, 'e': 1 }
Sum of absolute values of hashmap gives 3 and this shows that we must delete 3 characters ('a', 'c' and 'e' - 1 occurrence each) from strings A and B to make them anagrams.
susmithamenda Fixed the issue. Thanks for the help. Appreciate it!
Sort 1027 Discussions, By:
Please Login in order to post a comment