Problem Statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

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.

Example 1:

Input: s = "listen", t = "silent"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Example 3:

Input: s = "hello", t = "world"
Output: false

Constraints:

• 1 <= s.length, t.length <= 5 * 10⁵
• s and t consist of lowercase English letters.

Solution

We can solve this problem by calculating how many times each character appears in both the strings. If the frequency of each character is the same in both the given strings, we can conclude that the strings are anagrams of each other.

We can use a hash map to store the frequency of each character in both strings.

For each character in the string, the frequency of that character in string s is incremented and the frequency of that character in string t is decremented. After iterating over all characters in the strings, we will check if the frequency of all characters is 0. If it is, the strings are anagrams of each other and the function returns true. Otherwise, it returns false.

Code

Here is the code for this algorithm:

Time Complexity

The time complexity of this algorithm is O(n), where n is the length of the strings. This is because the algorithm iterates over each character in the strings once and performs a constant amount of work for each character.

Space Complexity

The space complexity of this algorithm is O(1), as the size of the hash map is proportional to the number of unique characters in the strings. In the worst case, all characters in the strings are unique, so the size of the hash map would be 26 (the number of letters in the alphabet).

However, in most cases, the number of unique characters is much smaller than 26, so the space complexity is closer to O(k), where k is the number of unique characters in the strings.