Valid Anagram

What do we need to check

In this question we are asked to check if two given strings s and t are anagrams of each other, that is with rearrangement of the letters of one of the strings whether we can create the other one. If so, we return True and False otherwise.

Below you can see some example inputs outputs and reasons behind them.

Example Inputs & Outputs

Constraints

Here we have some constraints for both our inputs and our resource usage (time and memory).

For the input we are sure that our strings are made of a-z characters of the English alphabet.

And for time complexity we are recommended to solve this question with O(m+n) time, m being the length of s and n being the length of t

For space complexity we are recommended to solve this question with O(1) space usage that is our usage of space should not depend on size of input.

When it comes to O(1) complexities we tend to think that our usage of that resource should be minimized. Yes this is the case at the end of the day, but minimum usage of a resource depends on the problem itself most of the time and it doesn't have to be that small always. O(1) doesn't mean that our usage is that small but rather it means usage doesn't increase with the input parameter's size. You just have to be sure that usage is limited to some constant value.

Common Approaches

There could be plenty of ways of solving this question but of course we have to meet the time and space constraints we mentioned above.

Sort Check

One way of solving this question could be first sorting both input strings (alphabetically) and then just comparing them. This could easily work because if two strings are anagrams of each other their sorted versions must be equal at the end.

With comparison-based sorting algorithms we could get O((m+n) log (m+n)) in time complexity, so they are not ideal to solve this question.

But there is another way of sorting our input strings here because we know that our inputs are limited to a-z characters. And that approach is Counting Sort, which is a non-comparison-based sorting algorithm and could be useful to us for this question. If you want to read more about Counting Sort, you can visit here.

In Counting Sort we basically store the counts of each character of the input string and then rearrange the characters to create the sorted string. I give you the snippet of it below, I am not going to go into detail, but you can get the general idea. After sorting, we just check equality of the strings.

def countingSort(s: str) -> str:
    # Count occurrences of each letter
    counts = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
    for ch in s:
        counts[ch] += 1
 
    # Rebuild the sorted string from the counts
    result = []
    for ch, count in counts.items():
        result.append(ch * count)
    return "".join(result)

Now this solution would work for sure, and we only iterate through the input once, so the time complexity would be O(m+n) here, which is OK. However, at the rebuilding phase we are using extra space to construct the sorted string and with that we are violating the space complexity constraint which is O(1) but we use O(n) to store the sorted version where n is the length of the individual strings.

As you can see, we need space for the rebuilding of the sorted strings, but in fact the question doesn't ask us anything about sorting the inputs, so we don't really need sorted versions of the strings and by just comparing the counts of the characters, we could determine if the strings are anagrams.

Solution with Hashmap Count

Different from the Counting Sort method, where we end up creating the sorted versions of the input strings, here we just store the counts of the characters, and check whether there are any inequalities in terms of character count.

In our solution code, we are not using two distinct counters for each of our strings, but rather we add +1 for each character occurrence in the first string and add -1 for each character occurrence in the second string, and check if counts are equal to 0 at the end. If this is the case for all characters, we can say that these two strings are anagrams of each other, so we return True. And when any one of the counts doesn't equal 0, we return False because we are catching an imbalance of one character in our strings, so we cannot create one from the other.

The time complexity of this solution is O(m+n). We are iterating through each string once, and a constant-sized dict once.

For space complexity, since we are just using a constant-sized dict, it is O(1). So we meet our constraints.

You can use two counters for each string and just compare the counters too if you want, but I wanted to do it in this way. It's up to you at this point, since it wouldn't make any difference in terms of complexity. I used the built-in type dict for my counter here, but there is another data structure in Python (and most likely similar data structures in other programming languages) called Counter. You can use that as well. If you want to learn about that, you can visit here

Below I am going to walk you through my solution. You can play the steps one by one to take a closer look at what's happening. I suggest you use pen and paper to spend some time on the solution to grasp the idea of it.

Code Walkthrough

First we are checking if the input strings s & t have the same length at line 2. Since if the strings are not of the same length, they cannot be anagrams as we saw in Example 3 above.

At line 3 we are initializing our hashmap with a-z lowercase letters and their count values to 0. We are going to use this hashmap as our counter in the solution.

In the first for loop at line 5 we are iterating through our strings together and for the string s we are counting in a positive manner, line 6, and for the second string t we are counting in a negative manner, line 7. For instance, for the letter a, for each occurrence in the string s we increase the count value by 1 and for each occurrence in the string t we decrease it by 1, and if the letter a occurs the same amount for both strings, its count value must end up as 0. That's the whole idea of the solution. Note that you could flip this choice of positive and negative count, and it wouldn't make any difference.

Python's zip function comes in handy for iterating through two iterable objects at the same time, and since strings are of the same length (we are sure about the length because we checked it at the beginning of our solution code), iteration won't have any imbalance.

In the second for loop we are just iterating through our counter alphabet values and checking if there are any count values different from 0. When we observe any, we just return False, since it means we have a letter with different amounts in our strings.

If all the count values are equal to 0, which means all characters occur at the same amount in both of the strings, we return True at the end of our solution.

Note that below I am showing just a fragment of the counter for the sake of simplicity.

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t): return False
    alphabet = {c: 0 for c in "abcdefghijklmnopqrstuvwxyz"}
 
    for i, j in zip(s, t):
        alphabet[i] += 1
        alphabet[j] -= 1
 
    for i in alphabet.values():
        if i != 0:
            return False
 
    return True

Follow Up

What if the strings were made of not only a-z characters but all Unicode characters? Would this approach still work? Or would we need to do some modifications here? Even after the modifications, would our complexity requirements still be ensured?

I'll leave these questions to you, and also I want to point out that the solution above is neither the shortest nor the most sophisticated solution, but rather it's written with fundamental data structures to help you grasp the idea of using Hashmaps.

Conclusion

Note that checking for anagrams is the same as checking Multiset Equality. Here we treat strings as a container and we could extend our solution to any collection type data structure. We are basically checking equality regardless of order here. For more information about Multiset Equality, you can visit this site.