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.
How would you go about reducing the other array? If you use a function like pop() it would take even more time as pop forces the interpreter to shift all the elements back by one.
@@elaborated-eggs You wouldn't need to pop it. Let me explain in a simplified example. Say you have an alphabet of three letters (abc) so you create an array with three 0's to represent the running count of each letter, let's call it histogram histogram = [0, 0, 0] By using a character encoding table we can subtract the starting letter, from the current letter of our string to determine the index in our array. python allows us to do this using the ord function: ord(a) returns 97 ord (b) returns 98 ord (c) returns 99 so if we do ord(a) - ord(a) it will return 0 ord(b) - ord(a) it will return 1 ord(c) - ord(a) it will return 2 Using a for loop we can build a histogram for char in "abba": index = ord(char) - ord('a') histogram[index] += 1 In this example abba would be mapped as [2, 2, 0] in our histogram array or [a*2, b*2, c*0] if we then run another for loop on our second string in reverse for char in "baab": index = ord(char) - ord('a') histogram[index] -= 1 It will zero out the histogram and return it to [0, 0, 0] if that's the case we return true, it was an anagram. if we had used abba and bab we would get [1, 0, 0] meaning we have a remainder of 1 a character and then we return false, it's not an anagram cause the letters didn't match. we could improve this by checking the length of the two words we are comparing, cause if they do not match they can't be anagrams..
@@elaborated-eggs as he mentioned histograms, I assume he would allocate an array of size 26, initially all at zero. When encountering a character, e.g. 'b', in the first string, we would increase the second entry of the array, just like in the approach in the video. The point is that there might be an unnecessary overhead when using hashmaps. In practice though, one would have to benchmark it in the specific language to really know (which most likely is not even an important bottleneck, so when you have a real job, this would not even matter!)
I solved this challenge in the following way. 1- making a loop with a for o while. 2- verifying that the first char in the string is the same that the last element and so on. 3 my base case and early return is when a character does not makes match I just return false. Btw, you only have to loop the half of the arr What do you think guys?
@@DjangoMx Sounds like you try too check for palindroms? This approach would not work for anagrams (unless you sorted one of them in ascending order and the order in descending order...)
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
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
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
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!
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.
@@zacherymcclendon3945 if the job requires performance, then they're using the wrong language... otherwise I would write a dll and you ctypes to still do it the same way.
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.
How does the " in " operator works in python , doesnt it just go through the entire list untill it finds the value ? Meaning you do : For c in t : if c in t
this doesn't work if s is longer than t and contains the example: s = "asdff" t = "asdf" this can be fixed by making sure they have the same length at the beggining
The first option is more efficient with counter. from collections import Counter class Solution: def isAnagram(self, s: str, t: str) -> bool: return Counter(s) == Counter(t)
Can you do better? If it's 26 letters (English alphabet, lowercase only), then an int array of size 26 would work. Lowercase the char and increment at index c - 'a'. where c is the character code. For the other string, decrement. Then checking is merely for(int i : array) if i != 0 return false; return true; Runs in O(m+n) where m and n are the length of the strings.
fun fact - in python your implementation, as well as the "better" implementation that this dude showed are both about the same or worse than the very first one that sorted the strings because sorted runs native code. There's literally zero reason to overengineer and overoptimize in python, unless you're willing to write a cpython module.
For some reason I thought about assigning x =0 And adding every letter from s as ASCII number. And then same thing with t, but removing. And if in the end x==0 then true. No idea how good this idea is, but solution is solution
OR public class Solution { public boolean isAnagram(String s, String t) { int[] alphabet = new int[26]; for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++; for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--; for (int i : alphabet) if (i != 0) return false; return true; } }
@@shashankkumar5166 Yes, "ate" and "tea" are indeed anagrams. Anagrams are words or phrases formed by rearranging the letters of another word or phrase, using all the original letters exactly once. In this case, by rearranging the letters in "ate," you can form the word "tea" and vice versa.
a_unique, a_count = np.unique(a, return_count=True); b_unique, b_count = np.unique(b, return_count=True); return a_unique.shape == b_unique.shape and np.all(a_unique == b_unique) and np.all(a_count == b_count); # didnt test, maybe a small error here or there but he idea is clear
And if you use cupy you will get a space complexity of n, work complexity of n log n and step complexity of the highest count (work + step complexity are the time complexity for parallel algorithms)
seriously first check length, if they do not even share the same length they aren't an anagram. Speed above everything. An an anagram must have the same letters, but also the same amount of letters. If you check first if they have the same length this will be faster then checking up till the last letter to see they do not share the same length even ... Leetcode my ...
That’s fair, but the main point is theoretical worst case time complexity and won’t change if you check the length. Although it would make the best case time complexity O(1) [you can get the length of a string in constant time in many languages]
Maybe I'm wrong but your basic thought "when anagrams are sorted, they got the same order" is not right. What if you have to different words with the same letters but different meaning. For Example in german there is the word "ampel" (Traffic light) and lampe (lamp). Both are sorted to AELMP, however, they are not anagrams.
![[UA] NAVI vs MOUZ | BO5 | IEM Rio 2024](http://i.ytimg.com/vi/CMBYk0cbGoA/mqdefault.jpg)
Master Data Structures & Algorithms For FREE at AlgoMap.io!
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.
How would you go about reducing the other array?
If you use a function like pop() it would take even more time as pop forces the interpreter to shift all the elements back by one.
@@elaborated-eggs
You wouldn't need to pop it.
Let me explain in a simplified example.
Say you have an alphabet of three letters (abc)
so you create an array with three 0's to represent the running count of each letter, let's call it histogram
histogram = [0, 0, 0]
By using a character encoding table we can subtract the starting letter, from the current letter of our string to determine the index in our array.
python allows us to do this using the ord function:
ord(a) returns 97
ord (b) returns 98
ord (c) returns 99
so if we do
ord(a) - ord(a) it will return 0
ord(b) - ord(a) it will return 1
ord(c) - ord(a) it will return 2
Using a for loop we can build a histogram
for char in "abba":
index = ord(char) - ord('a')
histogram[index] += 1
In this example abba would be mapped as
[2, 2, 0]
in our histogram array
or
[a*2, b*2, c*0]
if we then run another for loop on our second string in reverse
for char in "baab":
index = ord(char) - ord('a')
histogram[index] -= 1
It will zero out the histogram and return it to
[0, 0, 0]
if that's the case we return true, it was an anagram.
if we had used abba and bab we would get
[1, 0, 0]
meaning we have a remainder of 1 a character and then we return false, it's not an anagram cause the letters didn't match.
we could improve this by checking the length of the two words we are comparing, cause if they do not match they can't be anagrams..
@@elaborated-eggs as he mentioned histograms, I assume he would allocate an array of size 26, initially all at zero. When encountering a character, e.g. 'b', in the first string, we would increase the second entry of the array, just like in the approach in the video. The point is that there might be an unnecessary overhead when using hashmaps. In practice though, one would have to benchmark it in the specific language to really know (which most likely is not even an important bottleneck, so when you have a real job, this would not even matter!)
I solved this challenge in the following way.
1- making a loop with a for o while.
2- verifying that the first char in the string is the same that the last element and so on.
3 my base case and early return is when a character does not makes match I just return false. Btw, you only have to loop the half of the arr
What do you think guys?
@@DjangoMx Sounds like you try too check for palindroms? This approach would not work for anagrams (unless you sorted one of them in ascending order and the order in descending order...)
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
That's awesome, congrats!
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
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
from collections import Counter
return Counter(s) == Counter(t)
buddy ya cant import shit
says who, as long it's in-built you're good to go?@@warguy6474
@@warguy6474 it's base python lol
@EarlZMoade you still can't. Have you ever solved a Leetcode quesiton before?
no I haven't, but why would a company prevent you from using functions built into base Python? That doesn't make sense to me. @@warguy6474
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!
Yep
Shut up
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.
"Can you do better?"
No
"Why"
K.i.s.s - stand up and walk out... lol
-------------
Yeahhhhhh but what if the job requires performance driven work so time and space complexity matter a lot there’s times where you should optimize
@@zacherymcclendon3945 if the job requires performance, then they're using the wrong language... otherwise I would write a dll and you ctypes to still do it the same way.
You may use the alphabet counter and reduce the counter and return false if any position not zero this will run in O(n)
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.
Could also add an early return if the lengths of the strings don't match. Otherwise you run all that for nothing.
Hashmap was my first solution, although my code was sloppier than this. Learned about some new keywords in javascript when I cleaned it up.
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.
I agree!
for i in set(s):
if s.count(i) != t.count(i) or len(s) != len(t):
return False
return True
Why not just hash both to count then return the equality between both dicts?
Upon further thought its probably for less memory use
Equality for dictionaries is a little weird. You definitely could.
from collections import Counter
makes this trivial
You keep confusing algorithmic complexity with performance. Not the same thing at all.
I mean listen to this guy's fucking voice, people who know what they're doing don't conflate complexity with runtime performance 🤓🤓🤓🤓🤓
How does the " in " operator works in python , doesnt it just go through the entire list untill it finds the value ?
Meaning you do :
For c in t :
if c in t
It's if c in f: f is a dict so in is constant time searching is constant time for dict
The {} initialize a dictionary, not an array. That’s a very important distinction
this doesn't work if s is longer than t and contains the
example: s = "asdff" t = "asdf"
this can be fixed by making sure they have the same length at the beggining
The first option is more efficient with counter.
from collections import Counter
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)
return sorted(s) == sorted(t)
Can you do better?
If it's 26 letters (English alphabet, lowercase only), then an int array of size 26 would work. Lowercase the char and increment at index c - 'a'. where c is the character code.
For the other string, decrement.
Then checking is merely for(int i : array) if i != 0 return false; return true;
Runs in O(m+n) where m and n are the length of the strings.
I don't understand big O notation van you explain how it's O(1) instead of O(n)
@@drew.esbssy
It's not O(1), it's O(size of both strings)
I apologize if I screwed it up.
fun fact - in python your implementation, as well as the "better" implementation that this dude showed are both about the same or worse than the very first one that sorted the strings because sorted runs native code. There's literally zero reason to overengineer and overoptimize in python, unless you're willing to write a cpython module.
For some reason I thought about assigning x =0
And adding every letter from s as ASCII number. And then same thing with t, but removing. And if in the end x==0 then true.
No idea how good this idea is, but solution is solution
Creative, but incorrect. Consider "ac" and "bb"
I just solved this question yesterday with sorting approach
Aaaaaah yes something Ive never had to do in my software engineering job
Return Counter(s)==Counter(t) boom done
I thought all constants are removed when calculating O. Like O(2n)=O(n)
Yeah. Where do you see any constants?
OR
public class Solution {
public boolean isAnagram(String s, String t) {
int[] alphabet = new int[26];
for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++;
for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--;
for (int i : alphabet) if (i != 0) return false;
return true;
}
}
I like this one much better. Although it assumes lower case etc it saves the massive cost of hashing
It will have issues.
For example,
TEA and ATE are clearly not anagrams but still it will send an success result which actually wrong
@@shashankkumar5166
Yes, "ate" and "tea" are indeed anagrams. Anagrams are words or phrases formed by rearranging the letters of another word or phrase, using all the original letters exactly once. In this case, by rearranging the letters in "ate," you can form the word "tea" and vice versa.
@@lol-ng6kyah... Finally the explanation i need. I thought that anagram means the words that arranged backwards.
@@abuhabibah8448that’s a palindrome
Just convert it into ASCII and match the arrays?
a_unique, a_count = np.unique(a, return_count=True); b_unique, b_count = np.unique(b, return_count=True); return a_unique.shape == b_unique.shape and np.all(a_unique == b_unique) and np.all(a_count == b_count); # didnt test, maybe a small error here or there but he idea is clear
And if you use cupy you will get a space complexity of n, work complexity of n log n and step complexity of the highest count (work + step complexity are the time complexity for parallel algorithms)
return Counter(s) == Counter(t)
Yes this works! :)
Love these, keep it up! Thanks!
Awesome, thanks!
I was asked to do this recursively for some reason
seriously first check length, if they do not even share the same length they aren't an anagram. Speed above everything. An an anagram must have the same letters, but also the same amount of letters. If you check first if they have the same length this will be faster then checking up till the last letter to see they do not share the same length even ... Leetcode my ...
That’s fair, but the main point is theoretical worst case time complexity and won’t change if you check the length. Although it would make the best case time complexity O(1) [you can get the length of a string in constant time in many languages]
lmao the hash map is overkill here just use an array
nice algo, "👉👌🏿" is anagram of "👉🏿👌"
I also upload leetcode solutions
Whatever you say, Morty.
What is an anagram
Race is anagram of care. It really just means the counts of each used letter is the same
Maybe I'm wrong but your basic thought "when anagrams are sorted, they got the same order" is not right. What if you have to different words with the same letters but different meaning. For Example in german there is the word "ampel" (Traffic light) and lampe (lamp). Both are sorted to AELMP, however, they are not anagrams.
That is what an anagram is. I think you're confusing anagrams for something else.
@@duerdum9 oh damn, I was confusing it with palindromes. Nevermind, ignore me, i am an idiot x)
This aint even a better solution
it would be in other fully compiled languages tho
@@ДмитроПрищепа-д3я but we are only talking about his solution in the language he is using
Would love it more if you didn't pointlessly loop it. It reduces the professionalism by forcing it to succumb to youtube's technology trick
Meh
@@GregHogg yeah, you're meh. glad we agree.
return s == t[::-1]