Interview Question: Anagrams

[@farazromani]

Great video! Another edge case to mention is handling leading and trailing white spaces. Before the length check, you should also trim the two strings otherwise "ab " and "ba" won't pass.

[@ByteByByte]

that's a great point. it would definitely be good to trim first

[@iamvikasgola]

@@ByteByByte But we are considering all chars in given string. And space is in 256 chars. So we should not trim the strings as that space could be intentional.

[@vaibhavkumar38]

@@iamvikasgola Valid point.. Maybe this could be a clarification question to ask. should we retain leading and traiiling space or should we ignore leading and trailing spaces? Pls share your thoughts!

[@oleksandrknyga868]

Again, thanks for sharing! It is possible to do an iteration for s1 and s2 in the same array. For longer charspace then 256 I think HashSet would be more preferable.

[@wedding_photography]

HashMap, not HashSet.

[@antonyvilson8973]

Hi Sam, could you please tell me which is the best book for data structures and algorithms in Java, covering all the algorithms.

[@soudiptadutta6886]

We can use hashmap while solving this problem. The complete code is : class Abc1 { public static void main(String[] args) { String a = "Gini"; //String b = "iGin"; String b = "abcwd"; System.out.println(isAnagram(a,b)); } private static boolean isAnagram(String a, String b) { Map map = new HashMap(); for (int i = 0; i < a.length(); i++) { char ch = a.charAt(i); map.put(ch, map.getOrDefault(ch, 0) +1 ); }//for for (int i = 0; i < b.length(); i++) { char ch = b.charAt(i); if(!map.containsKey(ch)) {return false;} else { int count = map.get(ch); if(count == 0) return false; else {map.put(ch, count -1);} }//else } return true; } }

[@Bhavya0409]

What would be the difference if you used a HashMap to map the count of each character? does a map use more space than an int array of 256 slots? also, is there a benefit to using a for each loop vs a standard for loop, or is it just syntactical sugar?

[@ByteByByte]

Using a hashmap would be fine, but there is less overhead for an array and it's also just easier to manipulate the content. And theoretically you could use a single loop, but in this case the point is that each loop is iterating over a different string

[@Garensonic]

Hashmap also has O(n) space complexity but can be adapted to support Unicode characters. The 256 slot int array has constant space.

[@bkzlab]

Another approach would be to sort both (lowercase) strings or sequences of characters and then check if they (the sorted strings) are the same. Of course, the run time would be N logN (for each sort). Maybe the interviewer would expect you to come up with more than one solutions.

[@ByteByByte]

Yeah that's certainly another valid approach

[@lifeofme3172]

The last condition could be like if letter.length === 0 then return true (anagram) else false But thanks for the excellent tutorial. Really appreciate it.

[@3663johnny]

We can also resolve it in constant space complexity by just applying an XOR operation on the asci code of each character in the two string. If we end up with 0 then their anagrams.

[@ByteByByte]

Does that work in all cases?

[@3663johnny]

@@ByteByByte I think yes

[@wedding_photography]

Nope, that's wrong. Try it with "aa" and "bb". Will XOR to zero.

[@meghanachitta2847]

are not supposed to check if the string is null or empty before trying to access its length?? or while converting string to lower case. The above code will throw exception for empty strings.

[@remariorichards8237]

We actually dont need the entire ASCII character set, we can just use the HashMap which would be scoped to the actual letters, also we need to trim

[@erichlf]

In what world is 1

[@ByteByByte]

I mean we are literally referring to the number of different combinations of 8 bits... so in this case its because it IS a binary world

[@bloonfarmer3657]

do you need third for loop? Isn’t it do the same thing if can do the checking in the second for loop? If letter[c] is < 0. Return false.

[@oceanview-u8q]

def anagram1(s1, s2): letters = {} for ch in s1.lower(): if ch not in letters: letters[ch] = 1 else: letters[ch] += 1 for ch in s2.lower(): if ch not in letters: letters[ch] = 1 else: letters[ch] -= 1 for i in letters.values(): if i != 0: return False return True print(anagram1('ABCDE', 'edcba'))

[@posamnarmada4499]

Sir actually thanks for sharing this videos...but a humble request from my side is that would u please explain line by line of what's happening in each line ..sir...it will be helpful for the students like me who are new to programming...

[@fernandomederos6689]

Can someone explain me how can you put a Character in an array of integer I'm kinda confused

[@ByteByByte]

You aren't putting the characters into the array, you're just counting the number of occurrences of each

[@WWEckenman]

Wouldn't this version perform better than the one you mentioned? Keep up the good work! public boolean isAnagram(String s1, String s2) { if (s1.length() != s2.length()) return false; int[] letters = new int[256]; for (int i = 0; i < s1.length(); i++) { char c1 = Character.toLowerCase(s1.charAt(i)); char c2 = Character.toLowerCase(s2.charAt(i)); letters[c1]++; letters[c2]--; } for (int i : letters) { if (i != 0) return false; } return true; }

[@ByteByByte]

Maybe, maybe not. The time complexity is exactly the same either way. Remember that you count time complexity in terms of number of array accesses, so in your example, its N*2 + N, whereas mine is just N + N + N, both of which are O(3N) or O(N)

[@MrRys]

and if we used something like if(c >= 'A' && c

[@BrasilEmFatos]

You're so confident that u didn't even ran the code 😂😂 one day wanna be like you

[@ndimlo2906]

sorry, can someone please explain the int[1

[@ByteByByte]

it creates an array of length 256

[@crosscoss]

So you take number 1 which in binary is 0 0 0 0 0 0 0 1 (using the representation of an 8 bit/1 byte) and then you shift all the digits to the left ('

[@youtubeuseran]

@@crosscoss Thank you for the explaination

[@mohammadkamran7086]

Thanks bro.....

[@ByteByByte]

You're welcome

[@tomladdus9264]

Functional Swift, no worries about ASCII, more memory efficient in most cases: func isAnagram(_ a: String, _ b: String) -> Bool { var dict = a.lowercased().reduce(into: [Character: Int]()) { $0[$1, default: 0] += 1 } dict = b.lowercased().reduce(into: dict) { $0[$1, default: 0] -= 1 } return dict.values.reduce(true) { $0 && $1 == 0 } }

[@ranesh237]

Is it possible to use dynamic programming here?

[@ByteByByte]

Yes it's possible, but it wouldn't optimize anything

[@rod8128]

Thanks for the video. Just a typo: In the second loop it should be "char" instead of "chac", right?

[@MuteTelecast]

Why 256? ASCII has 128 characters.

[@ByteByByte]

A character in Java is 8 bits, so we're just accounting for every possible character. If you know they're ascii you could do something different

[@MirzaTalks36]

Another solution sort the two strings and check whether equal or not

[@dima9917]

is MotherInLow == WomanHitler tho?

[@sateforp]

public boolean isAnagram(String s1, String s2) { return si.isEqualIgnoreCase((new StringBuffer(s2)).reverse().toString()) Just reverse one string and compare?

[@ByteByByte]

I think you're thinking of palindromes. Anagrams can be ordered in any way as long as they have the same number of each character

[@huh_wtf]

I would suggest an alternative approach you could just sort'em and compare, after converting to lowercase.

[@ByteByByte]

anotherbuffer account yep there are a bunch of ways you can do this. That being said, what is the complexity of that solution?

[@huh_wtf]

Byte By Byte It's O(nlogn) coz we're sorting(comparison would take O(n) )....also we could hash the sorted strings and check if they produce the same hash. Couple of ways indeed!

[@ByteByByte]

Can you sort strings in less than O(nlogn) time?

[@sharjeeltahir5583]

What is anagram? At least explain that before you start.

[@oleksandrknyga868]

Imagine that you cut off letters from the word and mix them to create a new one. The new word you mixed is an anagram. If you a Harry Portter fan then good example might be I am Lord Voldemort Tom Marvolo Riddle MotherInLow WomanHitler

[@joshh.2802]

It isn't worth spending time on something like that when 90% of the people watching already know what it is, it isn't related to computer science, and it takes 5 seconds to google and find out if you happen to not know. I am personally grateful he doesn't take up a ton of time explaining every possible aspect of each question; let's just see the solution!

[@viaprenestina3894]

video starts at 5 minutes. talk talk

[@lmanerich]

You could only use 2 for's, in the second one you could check if the letter is 0 before decrement. for (Char c : s2.toCharArray()) { if (letters[c] == 0) return false; letters[c]--; }

[@antonyvilson8973]

Found one method to solve this. Find the ascii value and keep summing, if both sum is equal, then it's anagram. class Anagramtest{ public static void main (String args []) { int sum1=0; int sum2=0; String str1="amazon" ; String str2="amanoz" ; char c; if (str1.length() != str2.length()){ System.out.println("Strings are not anagram") ; return; } for(int i =0;i

[@shriduttkothari]

yes this should also solve and will reduce one loop

[@wedding_photography]

That is obviously incorrect. Try it with "ad" and "bc".