Valid Anagram

Intuition

Anagrams have identical character multisets, so if you add one for each letter of the first string and subtract one for each letter of the second, every tally must cancel out to zero. A quick length check rejects mismatched sizes early. If any count dips below zero during the subtraction pass, the second string has a surplus of some letter and cannot be an anagram.

Algorithm walkthrough

1. 1If the two strings differ in length, immediately return false.
2. 2Increment a count for every character in the first string.
3. 3Walk the second string and decrement the corresponding count.
4. 4If any count becomes negative, return false.
5. 5If the scan finishes without a negative count, return true.

Implementation

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        counts = {}
        for ch in s:
            counts[ch] = counts.get(ch, 0) + 1
        for ch in t:
            if counts.get(ch, 0) == 0:
                return False
            counts[ch] -= 1
        return True

Intuition

Sorting places letters in a canonical order, so two anagrams collapse to the exact same sorted sequence. This trades the linear counting pass for an O(n log n) sort, but it is compact and easy to reason about: if the sorted characters match position by position, the strings are anagrams.

Algorithm walkthrough

1. 1Return false right away if the lengths are unequal.
2. 2Copy each string into a mutable character sequence.
3. 3Sort both sequences alphabetically.
4. 4Compare the two sorted sequences element by element.
5. 5Return true only if they are exactly equal.

Implementation

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)