Valid Anagram

Problem

A spell-checker needs to verify that a user's retyped word is a valid rearrangement of the original. Given two strings s and t, return true if t is an anagram of s - that is, if t uses exactly the same characters as s, each the same number of times.

Example 1:

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

Example 2:

Input: s = "tab", t = "cab"
Output: false

Example 3:

Input: s = "abc", t = "ab"
Output: false
Explanation: the strings have different lengths.

Example 4:

Input: s = "", t = ""
Output: true
Explanation: two empty strings use exactly the same (zero) characters.

Constraints:

• 0 <= s.length, t.length <= 10^3
• s and t consist of lowercase English letters.

Solution Breakdown

Approach: frequency counting with Counter equality.

Two strings are anagrams exactly when they hold the same characters the same number of times - order is irrelevant. That definition is a statement about character frequencies, so the solution builds a frequency map for each string and compares the maps. First short-circuit on length: if len(s) != len(t) the strings cannot be anagrams, so return False before doing any counting. Then Counter(s) == Counter(t) builds both frequency dicts and compares them; dict equality checks that every key maps to the same count in both, which is precisely the anagram condition.

Counter is a dict subclass that tallies occurrences in one pass, so Counter("listen") is {l:1, i:1, s:1, t:1, e:1, n:1}. Two strings produce equal counters if and only if they are anagrams, so the comparison is the whole answer. Trace s="tab", t="cab": lengths match (3 == 3), Counter("tab") is {t:1,a:1,b:1} and Counter("cab") is {c:1,a:1,b:1}; they differ on t versus c, so equality is False. The length guard is not strictly required for correctness - unequal counters already differ - but it lets obvious mismatches exit without building any maps.

Edge cases: two empty strings pass the length check (0 == 0) and have equal empty counters, returning True; same-length strings with different letters ("aab" vs "abb") differ in counts and return False.

Complexity: O(n) time, O(k) space - one pass per string to count; k distinct characters stored (at most 26 for lowercase English, effectively O(1)).