Valid Anagram
Description: Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.
An anagram is a string that contains the same characters as another string, but the order of characters can be different.
Example 1:
Input: s = "racecar", t = "carrace" Output: true
Example 2:
Input: s = "jar", t = "jam" Output: false
Constraints:
s and t consist of lowercase English letters.
Recommended time and space complexity
You should aim for a solution with `O(n + m)` time complexity and `O(1)` space complexity, where `n` is the length of string `s` and `m` is the length of string `t`.
Hint 1
A simple solution is to sort the given strings and check if they are equal. This would be an `O(nlogn + mlogm)` solution. While this solution is acceptable, can you think of a better way without sorting the given strings?
Hint 2
By definition of anagrams, we can rearrange characters. Does the order of characters in both strings matter? Then what matters?
Hint 3
We can simply count the frequency of each character. We can do this using two separate hash tables for the two strings. Then we can check if the frequency of each character in string `s` equals the frequency in string `t` and vice versa.