Two strings are anagrams when one can be made by rearranging the letters of the other, using every letter exactly once. Given two strings s and t made of lowercase English letters, decide whether t is an anagram of s.
Examples
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Example 3:
Input: s = "a", t = "ab"
Output: false
Explanation: t has a letter s does not; lengths differing already settles it.
Example 4:
Input: s = "listen", t = "silent"
Output: true
Constraints
1 <= s.length, t.length <= 5 * 10^4
s and t consist of lowercase English letters.
Prerequisites
Hash sets and hash maps — expected O(1) membership and lookup, and what "expected" costs when hashes collide. Array traversal, and the habit of asking what a second pass buys over a nested loop.
How to think about it
1. Sorting
Intuition
Anagrams are the same multiset of letters, and sorting turns a multiset into a canonical string. Two words are anagrams exactly when their sorted forms match — a one-line answer worth having before reaching for counts.
Algorithm
1. If the lengths differ, they cannot be anagrams. 2. Sort both strings. 3. They are anagrams if the sorted forms are equal.
Time & Space
Time O(n log n) for the sorts. Space O(n) for the sorted copies (O(1) extra only if sorting in place is allowed).
2. Letter Counts Optimal
Intuition
Sorting computes more than the question asks for: an order nobody needs. Only the counts matter, and counting is linear. With a fixed alphabet the tally is at most 26 counts, which is why the space is O(1) rather than O(n).
Algorithm
1. Different lengths settle it immediately. 2. Walk s adding one to each letter's count. 3. Walk t: a count that is already zero means t has a letter s does not; otherwise subtract one. 4. Surviving both walks means every count returned to zero.
Time & Space
Time O(n). Space O(1) for a fixed alphabet — at most 26 counts regardless of input size.