LeetMotion
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Constraints:
1 <= s.length, t.length <= 5 * 104s and t consist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
Why this is a Hash Map problem
Hash maps provide O(1) average-case insert, delete, and lookup. They're used to count frequencies, track what you've seen, map elements to their indices, or group elements by a key. The classic use: convert an O(n²) nested-loop solution to O(n) by pre-processing with a hash map.
What do you want to look up in O(1)? Store that as the key. What information do you need about it? Store that as the value.
For "Two Sum": brute force checks all pairs O(n²). With a hash map, as you scan left-to-right, you store each element and its index. For each new element X, check if (target - X) is already in the map. One pass, O(n). The map makes "have I seen this before?" a O(1) question.
From brute force to optimal — understand every step of the journey
The hash map converts "search" operations from O(n) to O(1). The pattern is: "for each element, I need to quickly look up whether some related value exists" — store that related value as the key when you first encounter it. The one-pass trick works because: if a valid pair (a, b) exists, when you process b, a is already in the map (since a comes before b).