Valid Anagram

You'll replace sorting with counting: keep how many times each letter appears, and nothing else. You need strings and dictionaries. Related chapter: hash maps.

1. The problem

You get two strings of lowercase English letters. Return whether they use exactly the same letters, each the same number of times. Order doesn't matter, but counts do. This is LeetCode 242. Our function also handles empty strings.

"Same number of times" is the phrase that matters. "aab" and "abb" use the same two letters, but not equally often.

2. A correct baseline

def baseline(s,t):
    return sorted(s)==sorted(t)

assert baseline('listen','silent')
assert not baseline('aab','abb')
assert not baseline('a','')

Sorting both strings puts equal letters side by side, so anagrams sort to the same list. That takes O(n log n + m log m) time for strings of length n and m, and O(n + m) space for the sorted copies. On two strings of a million letters, that's about 40 million comparisons.

The bottleneck. Sorting puts every letter in order, but order is exactly what an anagram ignores. All you need is how many of each letter there are.

3. The observation

Count "listen": one each of l, i, s, t, e, n. Count "silent": the same. The counts match, so they're anagrams. Two strings are anagrams exactly when their letter counts match, so a hash map of counts is all you need to keep.

You don't even need a second hash map. First check the lengths: different lengths can never be anagrams. Then count the letters of s, and use up those counts while reading t. If t needs a letter whose count is already zero, you have your answer: not an anagram. This works because each string's letters can be counted independently of their order.

4. The solution and a trace

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        """Compare letter multiplicities; supports empty strings."""
        if len(s)!=len(t):
            return False
        counts={}
        for char in s:
            counts[char]=counts.get(char,0)+1
        for char in t:
            if counts.get(char,0)==0:
                return False
            counts[char]-=1
        return True

solve=Solution().isAnagram
assert solve('listen','silent')
assert not solve('aab','abb')
assert not solve('a','')
assert solve('','')

Trace s = "aab" and t = "aba":

Now try t = "abb" instead. The second b finds b at 0, so the function returns False right there.

5. Why it works

What stays true. Before each letter of t, counts holds the letters of s that haven't been matched yet. We only use a letter when its count is above zero, so no count goes negative.

A True answer is right. If every letter of t finds a match, every letter of t used up one letter of s. The lengths are equal, so every letter of s got used. That means the counts match exactly.

A False answer is right. The function returns False in two cases. Either the lengths differ, or t has more of some letter than s does. Both mean the counts don't match.

6. Cost, edge cases, and failure

Cost. One pass over each string: O(n + m) time on average, growing in step with the strings. With only 26 possible letters, the hash map never has more than 26 keys, so the extra space is O(1). With any characters allowed, space grows with the number of different characters. Python dictionary keys handle Unicode characters fine. Treating "A" and "a" as the same letter would be a different problem.

Edge cases. Two empty strings are anagrams. A string and an empty string are not, which the length check catches.

Where it fails. A set keeps which letters appear but not how often, so it can't replace the counts:

assert set('aab')==set('abb')
assert not solve('aab','abb')  # Counterexample to set equality as an anagram test.

import random
rng=random.Random(242)
for _ in range(1000):
    s=''.join(rng.choices('abcd',k=rng.randrange(20)))
    t=''.join(rng.sample(list(s),len(s))) if rng.randrange(2) else ''.join(rng.choices('abcd',k=rng.randrange(20)))
    assert solve(s,t)==baseline(s,t)