Valid Anagram - Leetcode 242 - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@virtumind]

if I got a job I will donate

[@ahmeddshabib]

@@virtumind do tell bro when you get the job

[@virtumind]

@@ahmeddshabib algorithms are very hard I can not understand all of them and other small companies want a person know 10 technologies at the same time. I gave up

[@ahmeddshabib]

@@virtumind No bro don't give up. I have been rejected more than 50 times now (Didnt count tho, It can be more than this). I started applying in March, still looking for a role 😀. Keep on trying .

[@virtumind]

@@ahmeddshabib compnies today want a superman or a robot

[@venkatasundararaman]

instead of having 2 count arrays, we can have a single count array and add +1 for s and -1 for t and finally run through each char and see if they are 0 in the count array. This will save more space complexity

[@sandeepi9519]

That's another way of saving space. That is a dictionary not array. Big difference in both of them. Searching a Key in Dictionary takes O(1) time. Searching a value in Array take O(n) time.

[@martinemanuel8239]

He talks about an array when every position it's a ascci number, arr[98] is the key and value is the count but in this case takes O(1) constant space at least in assci characters

[@iamdriy]

Yea, this is a valid way, but I would use something like a map from a char to an integer to represent the count. That way when you create your map from the letters of the first word, you just loop through the second word separately with constant look up time, decrementing the counts as needed.

[@aaronye4857]

This is exactly same as my solution, for your reference: class Solution: def isAnagram(self, s: str, t: str) -> bool: hashmap = {} for c in s: if c in hashmap: hashmap[c] = hashmap[c] + 1 else: hashmap[c] = 1 for c in t: if c in hashmap: count = hashmap[c] count -= 1 hashmap[c] = count else: return False for c in hashmap: if hashmap[c] != 0: return False return True

[@amulyakr]

@@aaronye4857 you can avoid the end for loop and simply check if set(hMap.values()) == {0}: return true

[@mostinho7]

Done thanks Given two strings determine if they’re anagrams Two possible solutions: 1. Use two hash maps for the count of each character then check that each character has same count in both (make sure strings are same length before cuz if they’re not then you know they can’t be anagram) 2. Sort the strings and compare them they should be identical

[@alexvallex5487]

why is using sorted(s)==sorted(t) not being used more frequently in this case?

[@DujiBuji]

Well if the number of characters stay the same (so are not part of the input n), the first solution with the hashmap has a space complexity of O(1). O(1) does not mean you do not need any more space, it just means you dont need more space, when the input gets larger. But even for very long strings, your hashmap will always be at least 26 entries long, hence O(1).

[@kyranzhanat9721]

I guess you meant "do not need any space" in the first half of your second sentence, am I right?

[@DujiBuji]

@@kyranzhanat9721 Yes, I think you are right. Too many "not"s in the sentence 😅 So theoretically, in O(1) you can still allocate a lot of memory. What matters is that the required memory does not grow as the input size grows, i.e. the required memory is bounded. And btw, this is also an important concept for interviews, if anyone is preparing. If the input consists of characters, you can try to take advantage of that (helped me in 2 of my interviews).

[@kyranzhanat9721]

@@DujiBuji 👍👍. Thank you a lot for your tip!

[@rabbyhossain6150]

This problem has a follow up challenge. "What if the inputs contain Unicode characters? How would you adapt your solution to such a case?". For that case it's not limited to just 26 characters.

[@saugatkarki3169]

@@DujiBuji Thank you for that gem of advice. Currently preparing for interviews!

[@joanchen8119]

May don't need two dictionaries, just one dictionary to store all chars in the s string, and loop through the t string, if the char in t is in the dictionary, just decrement 1 from it. At the end, check if each value is 0.

[@shikhar2811]

yeah i also came up with the same solution and it is more efficient as per on leetcode

[@joseelizondo9972]

I did the same, If len(s) and len(t) are equal then I looped through s made one dictionary with count of char in s, and then looped through T - checked if char existed in dictionary - decremented each char value in my map and then looped through my dictionary and made sure they were all 0. This is 3 loops of n size and I believe this make the runtime O(n * n * n) ~ O(3n) ~ O(n), and Space is O(s) ~ O(n) -> I'm still relearning bigO so please correct me if I'm mistaken. LeetCode said this was done in 30ms and used 13.8 MB of memory which beats 77.85% of other submissions.

[@joaocosta7981]

@@joseelizondo9972 I know this is an old comment but for future reference: O(n*n*n) is O(n^3). You mean O(n) + O(n) + O(n) = O(3n) = O(n).

[@joseelizondo9972]

@@joaocosta7981 you’re 100% right, def was supposed to be n+n+n

[@JumpCatStudio102]

Only need 1 loop to add dict and another loop to check if value of each key is 0: so its O(N) + O(N) for C# for (int i = 0; i < s.Length; i++) { var char1 = s[i]; var char2 = t[i]; if (!dict.TryAdd(char1, 1)) { dict[char1]++; } if (!dict.TryAdd(char2, -1)) { dict[char2]--; } }

[@frankl1]

Thanks for sharing this. I really enjoyed your materials. I have a solution using a single hash map: anytime I find a character in s the associated key in the hash map is incremented, and anytime I find a character in t, the associated key in the hash map is decremented. And finally, I only need to check if any value in the hash map is 0 to return True, otherwise, I return False.

[@tomrobinson5981]

This is my solution too, however, rather than checking if any value is 0 at the end, during the second loop I remove the key if it's value is 0 after decrementing. Then at the end I check if my hashmap is empty - if not, I return false. This is because I assume checking all values for 0 is O(n) because it is checking all values of an array. Checking for the existence of the hashmap at the end would be O(1).

[@saidjahonmamirov7355]

@@tomrobinson5981 That's really clever!

[@rohitsai6993]

Thank you for your consistent effort to upload a video everyday!

[@samarelsayed9347]

Thank you SO MUCH for the roadmap, it is so helpful as for this question, I was able to make a solution that has 45 ms runtime using the below code : from collections import Counter class Solution: def isAnagram(self, s: str, t: str) -> bool: l1 = list(s) l2 = list(t) if len(l1) == len(l2): r = list((Counter(l1) & Counter(l2)).elements()) if len(r) == len(l1) : return True return False else: return False

[@amirhoseinkalhor3475]

In the first solution, You don't actually need to iterate through the keys in the hash maps. Since hash maps don't have order if they are anagrams they will produce the same has maps you can just check if they're equal and if so return True else return False

[@skepticroadhog]

Would the time complexity still be O(n) in this case because '==' operation is O(n)?

[@unikaang1177]

wow thank you!! I test it, getting faster runtime without extra memory.

[@aisha-khan]

class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s)!=len(t): return False countS, countT = {}, {} for i in range(len(s)): countS[s[i]] = countS.get(s[i],0) + 1 countT[t[i]] = countT.get(t[i],0) + 1 if countS != countT: return False return True

[@kedarbikkannavar5907]

This!!

[@MykolaPavluchynskyi]

I think the most optimal solution for both time and space - using single array with size 26 for each character. it's constant space - O(1) and time O(n). When iterating s - increasing frequencies, when iterating t - decreasing. If array has only 0 at the end - it's anagram. Extra optimization - is to do extra check during traversal t - if current element become negative - we can do early return with false, but it's also extra check for each iteration - instead constant numbers of checks after 2 loops.

[@sumitdutta1087]

Good one! When I was coding it up, I came up with: class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False countS, countT = {}, {} for c in s: countS[c] = 1 + countS.get(c,0) for c in t: countT[c] = 1 + countT.get(c,0) return countS == countT

[@AkinduDasanayake]

Learning so many useful functions in this video (sorted, Counter, and .get()), thank you so much!

[@deepakparamesh8487]

Algorithm 1. Check if the length of s and t are unequal, if yes return false 2. Create Two maps sCount and tCount which will store the character count of both the strings a. Example : { 'a': 2, 'n':1} 3. Loop through either s or t string and Push the character count in the map for both s and t string. 4. Check if both the maps are equal once the loop is done. Time Complexity: O(len(S)) Space Complexity: O(1)

[@nicholashernandez1304]

The first solutions’ space complexity is not O(s+t) it is actually O( charSet) since you are storing a mapping from charSet to count. Assuming the charSet is constant then it should be O(1)

[@ok-cr3yd]

agree

[@omarllama]

Theoretically it's O(log(n) ). But, for this specific problem, and taking into account that we are using a programming language with fixed size integer, we can say the space complexity is O(1).

[@ThangNguyen-ul7hn]

@@omarllama can you explain why it's O(log(n)). I'm a bit confused, thank you!

[@DetectiveConan990v3]

as someone who just started Leetocode, I must say it feels good that I came up with solution 1 on my own. I know I have an incredibly long way to go but still, it means at least im not totally cooked

[@gabe5225]

Are you at FAANG now?

[@DetectiveConan990v3]

@@gabe5225 no

[@KotBinary]

Another way is to use only one HashMap. 1. Iterate the “s” saving char and its counter to the hashmap 2. Iterate “t” and instead of +1 the counter, do the opposite: -1. So, if s and t are equal you will have empty Hash Map (every value will be 0) You can improve the algorithm and have only one “for” iterating s and t I’m the same time.

[@Turmoiloaded]

the hash map space complexity ends up being O(1) regardless if you use two or one hashmaps because if you have two strings that are anagrams of one another and each one is 1 million characters long, the max size of the hash map is still 26 (max number of unique chars)

[@columbiars]

@KotBinary this is the best and simplest solution IMHO. I used the same

[@JaySwami]

you can do this in O(n) running time and O(1) space.. you can prime encode the 26 alphabets (2,3,5,7.....101) and your hashing function is just multiplying the encoded primes.. all anagrams will hash to the same value..this works for normal english word length strings well.. if you are dealing with hypothetical large strings.. this may not be the best approach.. if would optimize buy switching strategies based on length of the string

[@harishankarkarthik3570]

I disagree that solution 2 is O(1) space. Even if the sorting procedure takes O(1) space, sorting implies a modification of the input strings and so they must be counted towards the space complexity. Hence, the space complexity in the second solution is O(n). Funnily enough, the first solution does have an O(1) space solution since the map size is atmost 26 (constant).

[@InfinityOver0]

100% this. Neetcode really messed up the space complexities in this video. It will mislead a lot of people. Soln. 2 has SC of O(2n) = O(n), Soln. 1 has SC of O(1).

[@Vlad-qr5sf]

I solved it using an array in one for loop. Here is how: 1. Create a Frequency Table: It initializes a list letters_table of length 26, representing the 26 letters of the English alphabet, and sets all its elements to 0. This table will be used to keep track of the frequency of each letter. 2. Check Lengths: It then checks if the lengths of s and t are different. If they are, it immediately returns False, as anagrams must have the same number of letters. 3. Populate Frequency Table: For each character in s and t, it increments and decrements the corresponding entries in letters_table, respectively. For example, if s[i] is 'a', it increments letters_table[0], and if t[i] is 'a', it decrements letters_table[0]. 4. Check for Anagrams: Finally, it iterates over letters_table to check if all entries are 0. If they are, s and t are anagrams, and it returns True. Otherwise, it returns False.

[@draugno7]

For hash map approach, it is better to use one hash for both - decrement counts of every letter when traversing the second word and then check if the hash map has all 0s. We can stop iterating if count of a letter gets below 0

[@ahmedmhmouad7231]

we can make one freq array the S string increase the freq by 1 and T string decrease it by 1 and check if there is non-zero value in it at end

[@kyleanderson1043]

I think you could technically get away with using one hashmap and examining the other string and removing the value from the hashmap as you iterate through the opposite string. The problem also mentions that you are promised the characters are english lower case - this means there can be at most 26 different characters which would be constant memory in a hashmap application. I think the correct for speed is O(S+T) and for mem it's O(1).

[@abdul.arif2000]

line 11-13 is not needed u can jus put return countS == countT

[@lancetv4826]

The for c in countS is unnecessary. To check if two dictionaries have the same key-value pairs, you can compare the dictionaries directly using the == operator. Here's an example: dict1 = {"a": 1, "b": 2, "c": 3} dict2 = {"a": 1, "c": 3, "b": 2} if dict1 == dict2: print("The dictionaries have the same key-value pairs.") else: print("The dictionaries do not have the same key-value pairs.") output: The dictionaries have the same key-value pairs. Note that the order of the key-value pairs in a dictionary does not matter, as dictionaries are unordered collections in Python. The == operator compares the content of the dictionaries, not their order.

[@calidata]

You can compare two hash maps or dicts by directly comparing them: dict(A)==dict(B)

[@ChrisBenjamins]

Do you know what exact algo is used behind the scenes to check both dicts ? Who knows if they are optimized

[@OMGBEES1]

I think the first example is actually a time complexity of O(s + s + t), because you have to iterate over each string to build a frequency count in the respective hashmap. Then you have to iterate over the object keys of one hashmap to compare its frequency count to the other.

[@j.r.s8737]

technically yes, but since we drop the constants for the O notation, O(s+s+t) becomes O(2s+t), simplifies to just O(s + t) in the same way O(3n^2) is still considered O(n^2).

[@programming3043]

No, its actually O(s + s) because length of both the strings is 's'. So filling both the hash maps with frequencies would take just O(s) as it can be done in a single loop. Another O(s) to compare the frequencies in both the hash tables. So ultimately O(2s) drop the constants we get O(s) or O(n) where n is length of string. Space complexity = O(s) for first string and O(s) for another string. So total O(2s) ultimately-> O(s)

[@j.r.s8737]

@@programming3043 correct if we assume both strings are of the same length s, but it is possible for the inputs to not be of the same length. This is accounted for in lines 3-4 of neetcode's solution with the comparison of the lengths of the two strings, which I'm going to assume is a constant time operation. Otherwise if the same length then yes it is O(s).

[@kamran_desu]

Once we have counterS and counterT, why do we need to run a loop instead of simply: counterS == counterT?

[@jakub4062]

You don't run it. He just did insert it as an alternative solution to the previous one.

[@sadekjn]

if you take a look a the constraints of the problem. s and t consist of lowercase English letters. So space complexity will always be constant in the hash map solution since there can be at most 26 keys.

[@innerlion7564]

A much better anf simple solution is: Create a single map and insert elements and it's number of occurrence as key value pair of the first string. Then iterate over the next string. There will be 2 major scenerios- The element is not present in map, return false The element is present then if the value is > 0, decrement the value by 1 (--value) and increase a count variable by 1 (count++) If count == string1.length return true return false

[@draugno7]

What a relief that these two last tasks are easy!

[@konaraddi]

We're given the constraint that the strings will contain lowercase english letters only, so you can sort in O(n) time and O(1) space by using counting sort. function sort(str) { let charsToCount = new Array(26).fill(0) for (let i = 0; i < str.length; i++) { charsToCount[str.charCodeAt(i) - 97] += 1 } let sorted = "" for (let i = 0; i < 26; i++) { sorted += String.fromCharCode(i+97).repeat(charsToCount[i]) } return sorted } edit: above is in JavaScript

[@AlexSmith-mr4ps]

one interesting point is that in the final line "if countS[c] != countT.get(c,0):" the second parameter "0" is not necessary and removing it massively reduces runtime!

[@vert_sr]

immediately thought of that second solution as i was reading the problem. i was only able to because of your grouped anagrams video!

[@dmitributorchin]

Even if you assume that the sorting itself does not use extra space, since Strings in most languages are immutable, you will be using extra O(n) space as you'll need to create two new Strings.

[@darao99]

Another Solution that came up with using a list. class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False CharList = list(s) for i in t: if i in CharList: CharList.remove(i) if(len(CharList) == 0): return True return False

[@repetegaming3378]

Thanks for these videos, They are making me think more in terms of what is the most efficient way to solve a problem that isn't brute force. I think that using a hash map is not the most efficient way to solve this problem; I think sorting is more efficient. Here is my solution in java: class Solution { public boolean isAnagram(String s, String t) { char[] charS = s.toCharArray(); char[] charT = t.toCharArray(); Arrays.sort(charS); Arrays.sort(charT); String sortedS = new String(charS); String sortedT = new String(charT); return sortedS.equals(sortedT); } } There is no need to check the length of the two strings first; that is just wasted time and memory as at the end you are checking if the two sorted strings are equal.

[@wikihowsamples2972]

don't you waste time by comparing strings even when their length isn't equal? If many of the strings compared aren't equal then checking first will save a lot of time. Also, is it better to use Arrays.equals rather than first converting to a string to use String.equals?

[@repetegaming3378]

@@wikihowsamples2972 Thanks for asking these questions. No, you don't waste time when you compare the lengths of the two strings, but you do waste memory. It's also the same for using Arrays.equals (you would think it would be less memory used and not more).

[@Just_a_gamer48]

I really appreciate the work you do! I really do! Thank you so much, these videos have helped me have a better understanding !

[@yinglll7411]

Thank you for continuing this series!

[@as5728-h1i]

Just Found our channel. I'm preparing for a coding interview in a few months. Wish me luck

[@NeetCode]

Good luck!

[@janailtongoncalvesdesouza4160]

If we check the lowercased letters only, it would still be constant time with a O(26) memory used and an O(n) time where n is the length of the string, which should be equal btw

[@shivanshuchiha]

# Using Dictionary T.C: O(s+t) S.C: O(s) if len(s) != len(t): return False count = {} for x in s: if x in count: count[x] += 1 else: count[x] = 1 for x in t: if x in count: count[x] -= 1 if count[x] < 0: return False else: return False return True

[@NoCommentaryj]

I was asked this question similarly and i used Counter. I got the job. Sometimes using the built in tools provided by the language is better.

[@MrAarsan]

Will it work on Faang Companies Tho?

[@GoyfAscetic]

Fwiw, the problem's description offers no guarantees what case the characters can be used, so the sorting can fail if case is not accounted for. For example, cat and TAC might be anagrams but would not be equal strings after sorting in some languages such as Java IIRC.

[@BlackEternity]

class Solution: def isAnagram(self, s: str, t: str) -> bool: # check if the length of s and t are equal if len(s) != len(t): return False # declaring hashmap count = {} # check the next logic for i in range(len(s)): count[s[i]] = count.get(s[i], 0) + 1 count[t[i]] = count.get(t[i], 0) - 1 for c in count: if count[c] != 0: return False return True

[@musicgotmelike9668]

Hey, I just wanted to thank you for your great videos. Currently wokring on the Blind75 and all of your videos so far have been very useful! Even for example when I came up with a solution already (here e.g. with hashmaps) you show another way which is always interesting. Learned sth new:) Thx

[@Nashy119]

Would it be faster than sorting just to loop through the characters? You could remove the characters from the second word when matches as matches are found, giving you opportunities to end the loops early (match in inner loop can continue, no match in outer loop can break) and no need for a full string comparison at the end as you're only checking for an empty string. On the hashmap side I was thinking have one hashmap and subtract from the values.

[@17893great]

in Python, sorted(s) or s.sort() are using Timsort sorting algorithm. In this case, it won't be SC: O(1), instead of that, it should be O(n) which is the worst case.

[@psycho.banshee9350]

from itertools import permutations def isAnagram(self, s: str, t: str) -> bool: length = len(s) counter = 0 if len(s) == len(t): for x in permutations(s,length): tmp = "".join(x) if tmp == t: counter+=1 break if counter == 1: return True else: return False else: return False when the word is too long, then the solution is out of time

[@jatinnandwani6678]

Thanks Navdeep, you are excellent!

[@souravmoha2224]

s1="cat" s2="taca" z1=sorted(s1) z2=sorted(s2) if z1 == z2 : print("anangram") else: print("not anagram")

[@joseochoa3011]

Issue here would be time complexity because of sorting algorithm

[@sweetphilly2]

Something to else I found that made the Counter solution faster was to use "if not" vs "if...!=". Not too sure what happens under the hood that makes that the case

[@akjha627]

I think any solution which involves sorting is just too basic solution which the interviewer may not accept!. Better solution is to use just one hashmap to store the 1st anagram occurences and then while traversing the 2nd anagram, keep decrementing the values of the chars. If any one key is not found, return false. If while decrementing, you reach -1, return false...else return true finally. If the 2 string's length doesn't match, return false in the beginning itself. Code below! public bool IsAnagram(string s, string t) { var dictS = new Dictionary(); if (s.Length != t.Length) return false; //store the occurences in dictS foreach (char c in s) { if (dictS.ContainsKey(c)) dictS[c] += 1; else dictS.Add(c, 1); } foreach (char c in t) {// now check the occurences of chars in string t with the corresponding occurences in dictS if (dictS.ContainsKey(c)) {//if we reached 0 and since we found one more occurence, we will go below 0, means not an anagram if (dictS[c] == 0) return false; dictS[c] -= 1;// decrement the occurence } else return false;//if any char not found, it means not an anagram } return true;//if we reached, means its an anagram }

[@MrHorse16]

I saw the follow-up question on Leetcode “How would you adapt your solution if your input contains Unicode characters?” How would you solve this?

[@maheshrajput8491]

Using ASCII

[@maxresdefault8235]

you can do it in 3 lines if you use the sort function. if sorted(s) == sorted(t): return True return False

[@allo6596]

you dont even need to return like this. == always return true or false, its a one liner. return sorted(s) == sorted(t).

[@cricflix-channel]

This is much simpler I think ========================= import re a = "license" b = "silence" count = 0 for i in range(len(a)): if re.findall(a[i],b): count+=1 if count == len(a): print("Anagram") else: print("No")

[@kishlankashire5948]

I believe you don't have to loop through countS. Just write countS == countT and it'll compare. What do you say? I did that and it worked.

[@tintumarygeorge9309]

I really appreciate the work you do! I really do! Thank you so much, these videos are very helpful.

[@Abdullahkbc]

very clear solution but no need for the second loop. this would be enough ( if countT != countS: return False else: return True) i believe.

[@IkhlaqMalik]

Need not to maintain two HashMaps, You can use just one! public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; HashMap charFrequenyMap = new HashMap(); for (char ch : s.toCharArray()) { charFrequenyMap.put(ch, charFrequenyMap.getOrDefault(ch, 0) + 1 ); } for(char ch: t.toCharArray()){ if(charFrequenyMap.get(ch) == null) return false; charFrequenyMap.put(ch, charFrequenyMap.get(ch) -1 ); if(charFrequenyMap.get(ch) == 0){ charFrequenyMap.remove(ch); } } return charFrequenyMap.isEmpty(); }

[@appcolab]

You can add difault values like countS = defaultdict(lambda: 0) and just do countS[s[i]] += 1 This way, you won't get value does not exist from the hashmap the first time you adding.

[@mehdisaffar]

No need for lambda: 0, just write int which has 0 by default

[@tahmidsaad5765]

I'm at 4:02. So can't we just order both in ascending or descending order then find if they are equal or not?

[@heretoinfinity9300]

Thanks for the video. What about with the follow up question of Unicode?

[@WaldoTheWombat]

You actually only need one hash map: class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False hashmap = {} number_of_characters_to_clear = len(s) for char in s: hashmap[char] = hashmap.get(char, 0) + 1 for char in t: if char not in hashmap: return False hashmap[char] -= 1 if hashmap[char] == -1: return False number_of_characters_to_clear -= 1 return number_of_characters_to_clear == 0

[@Marco-sz6mq]

I think you can directly use one hash map as an array since the string just contains lowercase characters

[@akashrao7026]

I feel this is a better approach (hashmap method): if len(s) != len(t): return False d1 = dict() d2 = dict() for ele in s: d1[ele] = s.count(ele) for ele in t: d2[ele] = t.count(ele) if d1 == d2: return True return False

[@joshieval]

You can use one loop for this. You check to see if length of s is the same as length of t beforehand so you know it must be equal.

[@akashrao7026]

@@joshieval yes, you are right.

[@varunshrivastava2706]

Hey man, please make a DSA With Python playlist. Since there isn't any good course of dsa with python in the entire KZbin. Those who agree please hit like so that he see this comment.

[@shubhasheeshkundu9933]

Plzz make a video on dynamic programing using Python because there is no more video on KZbin DP with Python so we are all facing this problem plzz make one video and cover DP with Python.

[@sriram-uu6yd]

Check this series, its good. kzbin.info/www/bejne/oIXNg3qbZdyFrKs

[@anofranc]

Your videos are great! Quick que: So, at 11:29 looks like the sort() based solution has O(n) space complexity in the worst case. So, we didn't get to a solution with O(1) space complexity right?

[@DeepakChauhan-wu7ei]

O(n) is worst case but we can get O(1) as our best case, so we're kind of sloving space complexity problem

[@juandager5220]

Simplified Solution #1: class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False countS, countT = {},{} for char in s: if char in countS: countS[char]+=1 else: countS[char]=1 for char in t: if char in countT: countT[char]+=1 else: countT[char]=1 return countS == countT

[@aaronye4857]

Solution with only use one hashmap... class Solution: def isAnagram(self, s: str, t: str) -> bool: hashmap = {} for c in s: if c in hashmap: hashmap[c] = hashmap[c] + 1 else: hashmap[c] = 1 for c in t: if c in hashmap: count = hashmap[c] count -= 1 hashmap[c] = count else: return False for c in hashmap: if hashmap[c] != 0: return False return True

[@NexushasTaken]

yes this is O(1) memory space, but its not that efficient. the time complexity of this aproach is O(n*3) because it iterate s and t and also iterate the hasmap which have the same length as the strings

[@aaronye4857]

@@NexushasTaken No it's not, the time complexity is O(n*3) if you write it in triple for loop, it's separate loop so only need to count once in each, so is O(s+t+len(hashmap), simplify as O(n). you can test both code with sol1 and my code on leetcode, mine is faster.

[@deepblackoutlaw9640]

no soting, no hashmaps solution: public static bool IsAnagramByHashMap(string s, string t) { if (s.Length != t.Length) return false; int[] counter = new int[35]; for (int i = 0; i < s.Length; i++) { counter[s[i] - 97]++; counter[t[i] - 97]--; } foreach (int i in counter) if (i != 0) return false; return true; }

[@Silent.]

Love your videos, there's a cool optimisation you can do, however asymptomatically it would not matter, instead of having to hashMap's you can have one. This hashMap will store the val and frequencies of S, and what we do is loop through t, and then take away the values and a frequency of each. In the end we check that the hashMap has frequencies of 0, if not then we return False, else in the end we return True. This does increase Time complexity, but asymptomatically it won't matter

[@철수김-u5m]

9:11 do they ask these kinds of questions a lot? something like, 'since you have solved it this way, try to solve it by another way where you have to consider such as such'

[@87539319]

yeah that's a pretty common thing, the whole point is to see your thought process and how you work with others

[@besm_a]

Hello, Thank you for your videos :) Here is my solution class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False d=collections.defaultdict(int) for i in s: d[i] += 1 for i in t: if d[i]: d[i] -= 1 else: return False return True

[@LeonC0704]

class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False store = {} for letter in s: if letter in store: store[letter] += 1 else: store[letter] = 1 for letter in t: if letter in store: store[letter] -= 1 else: store[letter] = 1 for key in store: if store[key]!= 0: return False return True That solution seems to run faster.

[@patilshiv2288]

How about we add ASCII value of each character of string. If both addition are equal then true else false.

[@TheAlvaryn]

Simply adding the sum of each ASCII value of the char within both string inputs will not work 100% of the time. For example it will fail the following test case or similar below: "ac" = ord(a) + ord(c) = 196 "bb" = ord(b) + ord(b) = 196

[@HarimaKentaro]

tried with hashset for w.e reason didn't get it, was about to watch the video then just decided it to do the long way with sorting it and comparing each element in for loop. Worked fine :) at least got some kindda answer, gonna watch the solutions now :P Edit: I used hashset [just found can't repeat values, so that's out the window]. Tried using hashmap but failed. For reference, I am re-learning everything as it's been few years since I properly did programming. Getting back into it now, don't wanna waste my degree lool Edit2: Dam, that was stupid of me lol sorted then did the length check and on top of that each elements lool

[@nadavivry6503]

I thought of compering sorted lists at the first second, it cant be that easy 🤣

[@shanemarchan658]

var isAnagram = function (s, t) { const check = {}; for (let i = 0; i < s.length; i++) { check[s[i]] = check[s[i]] + 1 || 1; } for (let i = 0; i < t.length; i++) { if (!check[t[i]]) return false; check[t[i]] -= 1; } return s.length == t.length };

[@michelchaghoury9629]

This Channel is Awesome Please Keep going we need more and more content

[@mehulgoyal5-yeariddcivilen832]

if we done sorting then we store the string in a list data structure then how it reduces space complexity down to constant

[@basakar5912]

Great video! But I wonderding if the space complexity of sorted(s) == sorted(t) is actually O(n)? since sorted() will create a new list instead of sort the list in place.

[@tomerva22]

you could iterate the string 26 times counting each letter O(26*n)=O(n)/O(1)

[@SJHunter86]

You could make a character map as well to make it O(n) time with O(1) space def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False hashtable = [0 for x in range(26)] for i in range(len(s)): hashtable[ord(s[i]) - ord("a")] += 1 for j in range(len(t)): hashtable[ord(t[j]) - ord("a")] -= 1 if hashtable[ord(t[j]) - ord("a")] < 0: return False return True

[@frankl1]

@@SJHunter86 Nice solution, but I don't think it works if the strings include uppercase letters, or more generally any kind of character

[@SJHunter86]

@@frankl1 depends on the nature of the question being asked, yes. For either (using Python) you could just add a conditional to the top of the loop that says “if x.isalnum() and if y.isalnum()” and continue past that character if it isn’t, and use .lower() before adding it to the map to normalize the data. This particular LC question I remember says “you’re given a string with all lowercase characters and no special characters etc etc”

[@asong9695]

The space complexity can be just O(1) because there is constant amount of alphabet

[@bngplays945]

class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s)!=len(t): return False dic={i:0 for i in s} for i in s: dic[i]+=1 for i in t: try: dic[i]-=1 except KeyError: return False for i in s: if dic[i]==0: continue else: return False return True

[@sulhanfuadi]

thank youu for making this video!

[@Barons007]

Observing that anagrams have the same characters, if you sort them in lexicographical order the two strings would equal each other.

[@aaryamansharma3003]

can we use a brute force approach for it like in my code class Solution: def isAnagram(self, s: str, t: str) -> bool: for i in range(len(s)): for j in range(len(t)): if s[i] == t[j]: return True return False I know why it would fail, but is there a way to make it work?

[@abhishekbhatt454]

this is wrong way to do it. It'll return true once it gets the first matching string from the strings.

[@ishdemon_]

bdw you can do this using only one hashmap for(int i = 0; i

[@AbbyChau]

there is actually a better solution that you don't need to consume the memory by creating `countT`, by doing countS-- in the t's pass.

[@andrewferreira1261]

Genuine question. He's in the bottom quartile in terms of speed and memory for this solution. Is that good enough for interviewers in most cases? Do they only care about knowing a valid solution?

[@juandager5220]

When you submit a solution, Leetcode/Neetode gives you a time in seconds and shows a curve where your solution stands compared to others. However, this "performance" can be distorted due to how servers work in the back-end/cloud. Back to your question, interviewers care that the solution is valid, that you understand and know what you are doing, and that it is optimal or near optimal. For this, they care more about the Big O of your solution: Time and space complexity. TLDR: They care more about Big O.

[@HamidAli-ri9lv]

A Great Work Sir Thank for That Resource.

[@tonianev]

Doesn't sorted() use extra space? My understanding is that we'll want to sort in-place and therefore use sort()

[@adibhargava7055]

I believe you cannot use sort() on strings as they are immutable objects.

[@balavikashkandukuri6139]

@@adibhargava7055 yes exactly We can't use sort for strings

[@balavikashkandukuri6139]

@@adibhargava7055 instead we can store the str into a list and sort it and do the same for 2str. And Compare both the updated sorted lists. Although this isn't efficient since sorting takes nlogn

[@chiemerieokoro3038]

Very helpful. Thank you!

[@fun6324lkn]

The sorted function create a new array so it is actually spce complexity O(n)

[@sajjanparida]

How are two different hashmap stored in the same order ? Can you route me to any article or documentation to understand this better?

[@ytbcmt4686]

Charcode sum of 1st string - charcode sum of 2nd = 0 🤔

[@NeetCode]

That's a really good idea! I think it wouldn't work in some cases tho, where different characters can sum to the same value.

[@ytbcmt4686]

@@NeetCode Massive respect from India!!! This channel is incredibly underrated!!

[@namoan1216]

greate idea but Im not sure it passes all cases

[@pvcube66]

Can we use a single hashmap and store the count of all the letters in both string after that if for any character if its value is not a multiple of 2 they are not anagrams return false otherwise return true

[@deepblackoutlaw9640]

what if we have "aaaa" and "aa" the hashmap in this case contains ['a' : 6] 6 is multiple of 2 however the two strings are not anagrams

[@Jia-Tan]

Hey all, I have a question: Why are things called a 'hash _' when they don't have a hashing function? I noticed Neetcode calls what i'd call a 'map' a 'hashmap' and what I'd call just a 'set' a 'hashset'. AFAIK, for it to be a 'hashmap' the input would have to be converted to a hash before being mapped. Equally, for it to be a 'hashset' the input would have to be converted to a hash before being stored in a set data structure. If anyone can let me know I'd appreciate it!

[@xiaoyunliu8866]

u are my life-saver, dad