A word game accepts a guess only if it uses exactly the same letters as the given word, each one the same number of times, just possibly shuffled around.
Write is_rearrangement(a, b) -> bool that returns True if b can be obtained by reordering the letters of a, and False otherwise. A string counts as a reordering of itself.
is_rearrangement("listen", "silent") # True
is_rearrangement("aab", "abb") # False (different counts of 'a' and 'b')
is_rearrangement("cat", "cats") # False
is_rearrangement("", "") # True
Constraints:
0 <= len(a), len(b) <= 2 * 10^5- Both strings contain only lowercase English letters
a-z.
Crossing off each letter of a from a copy of b one at a time is O(n²). Aim for O(n) time.
Show hint
Two strings are reorderings of each other exactly when every letter occurs the same number of times in both. Tally one string, then untally the other.