Two strings are anagrams if the counts of their letters are equal. For example, these strings are anagrams, because the counts of each letter are the same:

To count the letters in a string, we want to loop through the string, and update the count of each letter that we've seen. To do this, we need to lookup/update the count of a letter quickly. We want a data structure that takes in a letter, and tells us the count of that letter, like this:

This data structure is a HashMap.

To code this up, we can create a HashMap for both strings with the count of each letter in it. After we build the hashmaps, we can compare them to see if they're equal. Here's the code for this:

Time Complexity: $O(n + m)$. We first build two hashmaps, each with 26 letters. This takes O(2 * 26) time, which is the same as O(1) time. We then loop through both strings, which takes a total of O(m + n) time. We then compare the two hashmaps, which takes O(26) = O(1) time. This gives a total of O(m + n) time.

Space Complexity: $O(1)$. We need to store two HashMaps, each with up to 26 entries. This requires O(2 * 26) units of memory, which is the same as O(1).

There's a minor optimization you can do. You can use just a single HashMap, which saves memory. You can do this by checking if the counts of the first string minus the counts of the 2nd string are all equal to 0. Here's the code for this:

Time Complexity $O(m+n)$

Space Complexity $O(1)$. This is O(26) instead of O(2*26) as earlier.