@@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
@@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 .
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
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
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.
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
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.
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 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).
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.
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.
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).
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
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.
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.
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]--; } }
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.
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)
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
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.
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)
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).
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
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.
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)
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
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).
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).
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
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).
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.
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.
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).
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)
@@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).
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!
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
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.
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
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.
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
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
# 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
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.
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) {
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.
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?
@@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).
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
Hey man, please make a DSA With Python playlist. Since there isn't any good course of dsa with python in the entire TH-cam. Those who agree please hit like so that he see this comment.
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.
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
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 }
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
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.
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")
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
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
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
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.
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
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.
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
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
@@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.
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
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; }
Plzz make a video on dynamic programing using Python because there is no more video on TH-cam DP with Python so we are all facing this problem plzz make one video and cover DP with Python.
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
I be pretty upset with that follow up question. In python sorting array might not take extra memory but sorting string does since strings are immutable. Similarly in js you need to convert string to an array to sort it first. So it just means the interviewer ignores the fact that sorting a string always takes extra memory.
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
@@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”
Isn't the first solution technically O(1) memory because we only ever need to store 52 items [as there are only 52 letters in the alphabet inc caps?] Like, when we increment the number of occurrences don't we not waste any memory?
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();
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?
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.
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?
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.
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?
@Neetcode Isn't the solution O(n) + O(1) in terms of time complexity and O(1) in terms of space complexity? Let me explain: if lengths are equal then, 1) First we use a single dictionary and loop it over to store counts count(s[i]) = counts.get(s[i], 0) + 1 and count(t[i]) = counts.get(t[i], 0) - 1. This would be O(s) 2) Now we loop through the hashmap to check if any count is != 0 then we return False else True. Here the hashmap would always have
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
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
if I got a job I will donate
@@virtumind do tell bro when you get the job
@@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
@@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 .
@@ahmeddshabib compnies today want a superman or a robot
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
why is using sorted(s)==sorted(t) not being used more frequently in this case?
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
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.
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
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.
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
@@aaronye4857 you can avoid the end for loop and simply check if set(hMap.values()) == {0}: return true
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).
I guess you meant "do not need any space" in the first half of your second sentence, am I right?
@@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).
@@DujiBuji 👍👍. Thank you a lot for your tip!
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.
@@DujiBuji Thank you for that gem of advice. Currently preparing for interviews!
Thank you for your consistent effort to upload a video everyday!
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.
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).
@@tomrobinson5981 That's really clever!
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
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.
yeah i also came up with the same solution and it is more efficient as per on leetcode
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.
@@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).
@@joaocosta7981 you’re 100% right, def was supposed to be n+n+n
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]--;
}
}
Learning so many useful functions in this video (sorted, Counter, and .get()), thank you so much!
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.
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)
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
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
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.
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)
agree
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).
@@omarllama can you explain why it's O(log(n)). I'm a bit confused, thank you!
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
Would the time complexity still be O(n) in this case because '==' operation is O(n)?
wow thank you!! I test it, getting faster runtime without extra memory.
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
This!!
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.
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)
@KotBinary this is the best and simplest solution IMHO. I used the same
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
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
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).
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).
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
immediately thought of that second solution as i was reading the problem. i was only able to because of your grouped anagrams video!
Just Found our channel. I'm preparing for a coding interview in a few months. Wish me luck
Good luck!
What a relief that these two last tasks are easy!
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).
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.
You can compare two hash maps or dicts by directly comparing them: dict(A)==dict(B)
Do you know what exact algo is used behind the scenes to check both dicts ? Who knows if they are optimized
line 11-13 is not needed
u can jus put
return countS == countT
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.
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).
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)
@@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).
Thank you for continuing this series!
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!
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
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.
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
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.
I really appreciate the work you do! I really do! Thank you so much, these videos have helped me have a better understanding !
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
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
Once we have counterS and counterT, why do we need to run a loop instead of simply: counterS == counterT?
You don't run it. He just did insert it as an alternative solution to the previous one.
# 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
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.
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
GOD BLESS YOU BROTHER FOR ALL YOU DO FOR US.
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.
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?
@@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).
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
Hey man, please make a DSA With Python playlist. Since there isn't any good course of dsa with python in the entire TH-cam. Those who agree please hit like so that he see this comment.
Thanks Navdeep, you are excellent!
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.
I really appreciate the work you do! I really do! Thank you so much, these videos are very helpful.
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
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
}
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
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.
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.
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")
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.
Will it work on Faang Companies Tho?
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
Thanks for the video. What about with the follow up question of Unicode?
s1="cat"
s2="taca"
z1=sorted(s1)
z2=sorted(s2)
if z1 == z2 :
print("anangram")
else:
print("not anagram")
Issue here would be time complexity because of sorting algorithm
you can do it in 3 lines if you use the sort function.
if sorted(s) == sorted(t):
return True
return False
you dont even need to return like this. == always return true or false, its a one liner. return sorted(s) == sorted(t).
very clear solution but no need for the second loop. this would be enough ( if countT != countS: return False else: return True) i believe.
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?
Using ASCII
I think you can directly use one hash map as an array since the string just contains lowercase characters
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
I thought of compering sorted lists at the first second, it cant be that easy 🤣
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
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.
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
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.
No need for lambda: 0, just write int which has 0 by default
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
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
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
@@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.
Observing that anagrams have the same characters, if you sort them in lexicographical order the two strings would equal each other.
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
u are my life-saver, dad
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;
}
Plzz make a video on dynamic programing using Python because there is no more video on TH-cam DP with Python so we are all facing this problem plzz make one video and cover DP with Python.
Check this series, its good. th-cam.com/video/jTjRGe0wRvI/w-d-xo.html
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
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.
@@joshieval yes, you are right.
My first thought actually was this "sorted" solution.
The space complexity can be just O(1) because there is constant amount of alphabet
This Channel is Awesome Please Keep going we need more and more content
I be pretty upset with that follow up question. In python sorting array might not take extra memory but sorting string does since strings are immutable.
Similarly in js you need to convert string to an array to sort it first. So it just means the interviewer ignores the fact that sorting a string always takes extra memory.
you could iterate the string 26 times counting each letter O(26*n)=O(n)/O(1)
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
@@SJHunter86 Nice solution, but I don't think it works if the strings include uppercase letters, or more generally any kind of character
@@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”
Isn't the first solution technically O(1) memory because we only ever need to store 52 items [as there are only 52 letters in the alphabet inc caps?]
Like, when we increment the number of occurrences don't we not waste any memory?
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.
Thank you for this informative video.
A Great Work Sir Thank for That Resource.
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();
}
Very helpful. Thank you!
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?
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.
thank youu for making this video!
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?
O(n) is worst case but we can get O(1) as our best case, so we're kind of sloving space complexity problem
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.
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?
this is wrong way to do it.
It'll return true once it gets the first matching string from the strings.
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
};
if we done sorting then we store the string in a list data structure then how it reduces space complexity down to constant
@Neetcode Isn't the solution O(n) + O(1) in terms of time complexity and O(1) in terms of space complexity? Let me explain:
if lengths are equal then,
1) First we use a single dictionary and loop it over to store counts count(s[i]) = counts.get(s[i], 0) + 1 and count(t[i]) = counts.get(t[i], 0) - 1. This would be O(s)
2) Now we loop through the hashmap to check if any count is != 0 then we return False else True. Here the hashmap would always have
How are two different hashmap stored in the same order ? Can you route me to any article or documentation to understand this better?
The sorted function create a new array so it is actually spce complexity O(n)
my solution is to sort s and t using the sorted() method and then compare them
How about we add ASCII value of each character of string. If both addition are equal then true else false.
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