Data Structures

Validate Anagrams

Given lowercase strings s and t, return whether the strings are anagrams of eachother.

Two strings are anagrams if the letters can be rearranged into each other.

First Few Test Cases:

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 number of letters 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)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)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. 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:

Mark as Completed:
Submits:
areAnagrams
Test your code to get an output here!
areAnagrams(
)
Test your code to get an output here!