Valid Anagram

easyFREEArrays & HashingBlind 75

Given two strings s and t, return True if t is an anagram of s, and False otherwise.

An anagram uses the exact same characters with the exact same frequencies.

Example

Input

anagram
nagaram

Output

True

Reasoning

Input: two lowercase strings, s = "anagram" and t = "nagaram". The question is whether the letters of $t$ are a rearrangement of the letters of $s$ , with order ignored entirely.
Tally the letters of $s$ : "anagram" has 7 letters, made up of a $\times 3$ , n $\times 1$ , g $\times 1$ , r $\times 1$ , m $\times 1$ (and $3+1+1+1+1 = 7$ ).
Tally the letters of $t$ : "nagaram" also has 7 letters, and its tally is again a $\times 3$ , n, g, r, m $\times 1$ each. Every letter appears in both strings, and no letter's count differs.
Output: identical tallies mean $t$ uses exactly the same letters with exactly the same frequencies, so the answer is True.
Notice: contrast s = "rat", t = "car". Both have 3 letters, but $t$ has a c that $s$ lacks and is missing the t, so the answer is False. Equal length is necessary but not sufficient. Strings of different lengths can never be anagrams, since some letter's count must differ.

Constraints

1 <= len(s), len(t) <= 5 * 10^4
s and t consist of lowercase English letters

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The concept of an anagram is crucial to understanding this problem. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. In the context of this problem, we're looking for a way to determine if two given strings are anagrams of each other. This involves checking if the two strings contain the same characters with the same frequencies.

To approach this problem, it's essential to understand the concept of frequency counting. Frequency counting is a technique used to count the number of occurrences of each character in a string. This can be achieved using various data structures, such as arrays or hash tables. In the context of this problem, we can use frequency counting to compare the character frequencies of the two input strings.

The hashing aspect of this problem is also important. Hashing refers to the process of mapping a large input (in this case, a string) to a smaller, fixed-size output (such as an array or hash table). This allows us to efficiently store and compare the character frequencies of the two input strings. Understanding how to use hashing to solve this problem will be key to finding an efficient solution.

Algorithm/Approach

The general approach to solving this problem involves using a hash-based algorithm to compare the character frequencies of the two input strings. This can be achieved by creating a frequency table for each string, which stores the count of each character in the string. We can then compare the two frequency tables to determine if the strings are anagrams of each other.

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a frequency table for each input string, using a data structure such as an array or hash table.
Iterate through each character in the input strings, updating the corresponding count in the frequency table.
Compare the two frequency tables to determine if the strings are anagrams of each other.
If the frequency tables are identical, return True, indicating that the strings are anagrams. Otherwise, return False.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Failing to handle edge cases, such as empty strings or strings with different lengths.
Using an inefficient data structure, such as a linked list, to store the frequency table.
Not properly comparing the frequency tables, leading to incorrect results.

Time & Space Complexity

The expected time complexity for this problem is $O(n)$ , where $n$ is the length of the input strings. This is because we need to iterate through each character in the input strings to create the frequency tables. The expected space complexity is also $O(n)$ , as we need to store the frequency tables in memory. However, in practice, the space complexity will be $O(k)$ , where $k$ is the size of the character set (e.g., 26 for lowercase letters), since we only need to store the count of each unique character.

solution.py

Python 3.13

Test results