anirudherabelly Java implementation of the problem!!
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner sc=new Scanner(System.in); String s1=sc.nextLine(); String s2=sc.nextLine(); int cArr[]=new int[26]; int cArr1[]=new int[26]; for(int i=0;i<s1.length();i++)cArr[s1.charAt(i)-97]++; for(int i=0;i<s2.length();i++)cArr1[s2.charAt(i)-97]++; int count=0; for(int i=0;i<26;i++)count+=Math.abs(cArr[i]-cArr1[i]); System.out.println(count); }}
ivdekov Could you explain your approach to the problem? What does the line
cArr[s1.charAt(i)-97]++do?
chunktri 97 is the ASCII code of character a. Since the string only consist of lower case letters, there's an array of size 26. To store the count of letter a means subtract 97 from character and add one to it's array value
arjun033 nice!
jeffreyeffendy_1 You can just use one array here to store. Here is a better version of your code. I am halving your space requirement by 26 * 4 bytes.
int cArr[]=new int[26]; for(int i=0;i<s1.length();i++)cArr[s1.charAt(i)-97]++; for(int i=0;i<s2.length();i++)cArr[s2.charAt(i)-97]--; int count=0; for(int i=0;i<26;i++)count+=Math.abs(cArr[i]); System.out.println(count);Cheers!
jfuji6 Nice optimization!
onlysumon We can swap the string and reduce the count loop from O(len(s1)) + O(len(s2)) to O(max(len(s1), len(s2)).
sicter This solution with some syntactic sugar:
int[] chars = new int[26]; for (char c1 : s1.toCharArray()) { chars[c1-97]++; } for (char c2 : s2.toCharArray()) { chars[c2-97]--; } int count = 0; for(int i: chars) {count += Math.abs(i);} System.out.println(count);Note on for-each in Java- http://stackoverflow.com/a/256861/3527434
davidrieper61 Loved this man.
ajanacs [deleted]ajanacs How did this work?
uchiha111 nice one buddy!!!!
zakiralig184 Cool bro!!!! ur code optimization!!!!!!
adityamalhotra11 Instead of using an array of size 26, why not use a hashMap, which will have a size 26 in the worst case and in other cases, always less than that. This reduces space complexity and time pretty much remains O(n).
mahashwetha91 yes if theres is like 10 letter max may be of same ,we wont be using space.
bingo_22 This approach has been immensely helpful. Thanks a lot.
anirudherabelly thankU!! @anmol_1995
lonewolff my java logic goes like this
public static void main(String[] args) { Scanner sc=new Scanner(System.in); String s1=sc.next(); String s2=sc.next(); int d=0; for(int i=0,k;i<s1.length();i++) if((k=s2.indexOf(s1.charAt(i)))!=-1) { s2=s2.substring(0,k)+s2.substring(k+1); d++; } System.out.println(s1.length()+s2.length()-d); }
Embaby the searching in a string is a little cost ;it's about log (n) or n complexity .thus,your algorithm is big omega of nlog(n). instead you can use dictionary(HashMap) to make your algorithm kind of O(n)
voiceofall I don't understand the solution. What about the test case: "cde", "adc". The result should be 4 not 2.
Iancarson01 Check on your "d" and "c",delete e and a =2
15131A05K8_ nice logic
cse_115 nice..
ayushjain_creat1 There is no need of posting code for such easy problems.
fernando_luz I made a similar answer in C++, using unordered_map.
int makingAnagrams(const string &s1, const string &s2){ unordered_map<char, int> letters; for(char c: s1){ ++letters[c]; } for(char c: s2){ --letters[c]; } int countDeletions = 0; for(pair<char, int> pr: letters){ if (pr.second != 0){ countDeletions += abs(pr.second); } } return countDeletions; }
ayushjain_creat1 You just traslated his code too c++..
fernando_luz I use only one container to store the letters instead 2 containers.
And I reach the solution without check the discussion forum.
More differences:
- I use unordered_map providing a fastest lookup to an element;
- I check another improvement in the code, I dont need the if conditional inside the last loop to counter the values.
- I use prefix increment instead pos fix increment.
int makingAnagrams(const string &s1, const string &s2){ unordered_map<char, int> letters; for(char c: s1){ ++letters[c]; } for(char c: s2){ --letters[c]; } int countDeletions = 0; for(pair<char, int> pr: letters){ countDeletions += abs(pr.second); } return countDeletions; }
This solution is very elegant. :-)
manoj_banik_cs Your solution is good. But you can avoid map, just a single int array can serve the purpose. I did it, even i didn't use the "abs" function also.
sachetwasti61 I had done something similar but only two testcases pass why?
import java.util.*; import java.io.*; public class Hack45{ static PrintStream p = System.out; static int [] arr = new int[26]; public static void main(String[] args){ StringBuilder sb = new StringBuilder(); String s,s1; Scanner in = new Scanner(System.in); s = in.next(); s1 = in.next(); int i; for(i=0; i<s.length(); i++){ arr[s.charAt(i)-'a']++; } for(i=0; i<s1.length(); i++){ if(arr[s1.charAt(i)-'a']!=0) arr[s1.charAt(i)-'a']--; else arr[s1.charAt(i)-'a']++; } int count = 0; for(i=0; i<26; i++){ count+=arr[i]; } p.println(count); } }
sarathy_v_krish1 C++ solution :
int makingAnagrams(string s1, string s2) { map<char, int> m1, m2; int deletions=0; for (char ch:s1) m1[ch]++; for (char ch:s2) m2[ch]++; for (int i=0;i<26;i++) deletions+=abs(m1['a'+i]-m2['a'+i]); return deletions; }
pawankushwah850 string s1,s2; cin>>s1>>s2; int co=0; for(char i='a'; i<='z'; i++) co+=abs(count(s1.begin(), s1.end(),i)-count(s2.begin(), s2.end(),i)); cout<<co; return 0;sarathy_v_krish1 Looks smaller, yes, but you are iterating over each string 26 times...less efficient.
amit_raj_cse20 Python Oneliner Code
def makingAnagrams(s1, s2): return len(s1)+len(s2)-2*(len(s1)-sum((Counter(s1)-Counter(s2)).values()))
kris_tobiasson Here is my JS solution:
let ar2 = s2.split(``); let ab = Math.abs(s1.length - s2.length); for(let i = 0; i < s1.length; i++){ let id = ar2.indexOf(s1.charAt(i)); if(id !== -1){ ar2.splice(id, 1); } } return (s1.length<s2.length) ? (ar2.length-ab) * 2 + ab : (ar2.length) * 2 + ab;
DomNomNom 4 clean lines - python3
from collections import Counter counts = Counter(input()) counts.subtract(input()) print(sum(abs(x) for x in counts.values()))
glegoux [deleted]abhishekscript from collections import Counter a=Counter(raw_input()) b=Counter(raw_input()) print sum( ((a-b).values()) + ((b-a).values()) )
Done without loop
tasdemir_nuri What about sum(). Isn't that a loop?
abhishekscript Obviously it is. What I meant is
print(sum(abs(x) for x in counts.values()))
and this
print sum( ((a-b).values()) + ((b-a).values()) )
without for. Thanks
kevindu [deleted]Norman99 Nice. I need to learn how to use Counter!
My solution with defaultdict:
from collections import defaultdict def count_chars(word): counts = defaultdict(lambda: 0) for ch in word: counts[ch] += 1 return counts word1, word2 = count_chars(input()), count_chars(input()) allchars = set(list(word1.keys()) + list(word2.keys())) print(sum(abs(word1[ch] - word2[ch]) for ch in allchars))
lucinda04zhang create dicts in one line and without the library
all_keys = set(s1 + s2) k1 = {i:s1.count(i) for i in all_keys} k2 = {i:s2.count(i) for i in all_keys}
meacreatio Thanks for giving a great example of some of the cool stuff
Countercan do.
manoharsingh2110 Need to learn python after seeing this :)
DivJain def makingAnagrams(s1, s2): s3=list(s2) for i in s1: if i in s3: s3.remove(i) no_common=len(s2)-len(s3) return len(s1)+len(s2)-2*no_common
My Solution
akhileshjoshi123 pure set concept illustration :) thanks !
alex_zehet cool solution!
mike_buttery Thanks your code helped. Version without import.
def makingAnagrams(s1, s2): d = {c:s1.count(c) for c in set(s1)} for c in s2: d[c] = d.get(c, 0) - 1 return sum(map(abs, d.values()))
snkt_pat2 passed all test cases in 0s
string in1,in2; cin>>in1>>in2; int array[26] = {0}; for(int i=0;i<in1.length();i++) array[in1[i]-'a']++; for(int i=0;i<in2.length();i++) array[in2[i]-'a']--; int sum = 0; for(int i=0;i<26;i++) sum+=abs(array[i]); cout<<sum; return 0;
bazuka_ what is the prolem with my code it passes all the test casses except three cases.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int max (int a,int b){return a>b?a:b;} int main() { string s2,s1;int a[123]={0},b[123]={0},cnt=0; cin>>s1>>s2; for(int j=0;j<max(s1.size(),s2.size());j++) { a[s1[j]]++;b[s2[j]]++;} for(int j=97;j<123;j++) if(a[j]!=b[j]) cnt+=abs(a[j]-b[j]); cout<<cnt; /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }
mohitthapark include
include
include
include
include
using namespace std;
int main() { string s2,s1; int a[123]={0},b[123]={0},cnt=0; cin>>s1>>s2; for(int j=0;j<(s1.size());j++) { a[s1[j]]++; } for(int i=0;i<(s2.size());i++) { b[s2[i]]++; } /for(int j=97;j<123;j++) {cout</ for(int j=97;j<123;j++) if(a[j]!=b[j]) { cnt+=abs(a[j]-b[j]); //cout<
cout<<cnt; /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0;}
check out your code for test case: aaaaaaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb It is overwriting the value of array a 2 times
sunitswn91 j<max(s1.size(),s2.size())
You are accessing an array (either a or b depending on whose size is lesser) beyond its range, the behaviour might be undefined.
zeyad1998 can you explain to me the logic behind your code?
Dhruv_94 [deleted]Dhruv_94 Hey, do you mind explaining what the bold part does exactly? Thanks!
for(int i=0;i<in1.length();i++) **array[in1[i]-'a']++;** for(int i=0;i<in2.length();i++) **array[in2[i]-'a']--;**
zeyad1998 he puts the no. of letter in its correct no. in the alphabet array he made. and ++ means he increment this place by 1
dineshnadimpalli Awesome logic! Loved it!
snkt_pat2 Thank you so much
khoangcachxalam1 thanks for your good idea !although i do not still know all images your code !
ankushrasgon07 def makingAnagrams(s1, s2): for i in s1: if i in s2: s1=s1.replace(i,"",1) s2=s2.replace(i,"",1) return(len(s1)+len(s2))
Here is my simple python 3 solution
man198407 def Making_Anagrams(s1, s2):
same = 0 s1 = list(s1) s2 = list(s2) for i in s1: if i in s2: s2.remove(i) same += 1 return (len(s1) - same) + len(s2)
Sort 419 Discussions, By:
Please Login in order to post a comment