Valid Anagram

The problem description can be found in LeetCode.

Approach

From the constraints we can see that both input strings (s and t) consist of lowercase English letters.

The first assumption we can make is that if the length of the two strings is different, t will not be an anagram of s.

Since we know that the length of the two strings must be the same, if we order all the characters of the two strings and the strings are equal, it means that t is an anagram of s. However, this would require $O(2nlogn+n)$, hence $O(nlogn)$, for sorting both strings and then comparing them, where $n$ is the length of the two strings.

Of course, we can do better in terms of time. In fact, we could simply count the characters of both strings and then compare the two counters to confirm that t is an anagram of s.

For example, for the strings "asd" a "sad", we would have:

s = "asd"
t = "sad"

counter_s = {
    "a": 1,
    "s": 1,
    "d": 1,
}

counter_t = {
    "s": 1,
    "a": 1,
    "d": 1,
}

assert(counter_s == counter_t)

The counters are the same, hence, we can return True.

Solution

Since our alphabet is limited to lowercase English characters, we can use a static list of 26 elements, instead of a dictionary. The letter a is mapped to index 0 and z to 25.

Solution

from typing import List


class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        return self.get_chars_counter(s) == self.get_chars_counter(t)

    def get_chars_counter(self, s: str) -> List[int]:
        m = [0] * 26

        for char in s:
            idx = ord(char) - ord("a")
            m[idx] += 1

        return m

We could also use a normal dictionary:

from collections import defaultdict
from typing import DefaultDict


class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        return self.get_chars_counter(s) == self.get_chars_counter(t)

    def get_chars_counter(self, s: str) -> DefaultDict[int, int]:
        counter: DefaultDict[int, int] = defaultdict(int)

        for char in s:
            idx = ord(char) - ord("a")
            counter[idx] += 1

        return counter

As well as the built-in Counter:

from collections import Counter


class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        return self.get_chars_counter(s) == self.get_chars_counter(t)

    def get_chars_counter(self, s: str) -> Counter:
        return Counter(s)

Complexity

• Time: $O(n)$
• Space: $O(1)$

Where $n$ is the length of the strings s and t.