Google Interview Question! | Valid Anagram - Leetcode 242

leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[clehaxze]

The entire lower case alphabet has 26 characters. Using a hash map probably slower due to the overhead of hashing. I think the optimal solution is to use an array, build the histograms using one string and reduce with another. Finally sum up the absolute value of each bin.

[siddharthgawande]

We can create hashmap of first string with character-count pair
And iterate over second string’s characters and count -=1 if it’s found
As soon as any count becomes < 0 or character not present in hashmap we can flag as False and break

This will take less space as only one hashmap is created

[_deathcry]

Lol, that's exactly the one I got for my job interview, made both solutions described here in kotlin, one easy to read with sort and second for maximum performance some iterating with hashmap, working there for 2 weeks already.

Thing to note - anagram is about letters, so to be safe - before sorting filter out the letters

[akex]

from collections import Counter
return Counter(s) == Counter(t)

[RkTruth]

"Can you do better?"
No
"Why"
K.i.s.s - stand up and walk out... lol

[coolkaw]

Crazy how quick I solved this problem using the same second method you showed. Looks like the 70 leetcode I’ve done so far are actually making me better at this stuff!

[mazthespaz]

after making sure both strings are the same length, you can make your own hash function to hash both strings to large integers and just compare the numbers. already implemented it in code and works fast and fine unless the test strings are really long

[nifegun]

Or iterate both strings in lockstep, where each string adds 1 or -1 to its repsect value in the map. Have another variable that counts up when you entered a new value to the map and counts down when youve set a value back to zero. Return that counter == 0. O(n) since they have to both be the same length anyway. Plus only 1 loop in the code. Also you know you only have 26 or 52 (if caps are present in input) values available, so you could just build an array of zeroes to start off and now thats constant memory too.

[selvakumar-zbtb]

You may use the alphabet counter and reduce the counter and return false if any position not zero this will run in O(n)

[MrIrishBoss]

for i in set(s):
if s.count(i) != t.count(i) or len(s) != len(t):
return False
return True

[sorcdk]

And the constants in setting up a hash and checking through are so large that by the time you are done with those constant time operations the sorting version is already done with solving the entire problem. That is, if you were not using Python, because in Python there are just so much overhead on each operation that you would not notice the cost.

[grafstahl]

Could also add an early return if the lengths of the strings don't match. Otherwise you run all that for nothing.

[AnthonyCastrio]

Hashmap was my first solution, although my code was sloppier than this. Learned about some new keywords in javascript when I cleaned it up.

[RS-fzps]

Honestly, I would be the most impressed with both answers in this exact order. First do it quick and simple, then do it slow and smart.

[jojomark]

from collections import Counter
makes this trivial

[dacjames]

You keep confusing algorithmic complexity with performance. Not the same thing at all.

[RobbyRyanson]

yes something Ive never had to do in my software engineering job

[averagestanduser]

Why not just hash both to count then return the equality between both dicts?

Upon further thought its probably for less memory use

[Noobiee_FPS]

I just solved this question yesterday with sorting approach