Find List Entries That Are Anagrams of a Target
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
Given a list of lowercase strings and a lowercase target string, return every list entry that is an anagram of the target, preserving its original list order. Duplicate matching entries at different positions remain duplicated in the output.
### Function Contract
Implement `find_anagrams(words, target) -> list[str]`.
### Constraints
- `0 <= len(words) <= 200000`.
- Every string contains only lowercase English letters and has length at most 200.
- Two strings are anagrams only when every character count matches exactly.
- The input list must not be mutated.
### Examples
- Words `["listen","silent","list","enlist","silent"]` and target `"listen"` return `["listen","silent","enlist","silent"]`.
- An empty target matches only empty strings.
```hint Use a canonical key
For a fixed alphabet, a 26-count tuple avoids sorting each string and makes length mismatches cheap to reject.
```
### Edge Cases
- Repeated letters must have equal multiplicity.
- A word with the right letters plus one extra letter is not a match.
- Duplicate matching strings are preserved.
Quick Answer: Return list entries that are exact anagrams of a lowercase target by comparing character counts, preserving input order and duplicate matches while rejecting length or multiplicity differences.
Given a list of lowercase English strings and a lowercase target string, return every list entry whose character counts exactly match the target's counts. Preserve original list order, preserve duplicate matching entries from different positions, and do not mutate the input list. An empty target matches only empty strings.
Constraints
- 0 <= len(words) <= 200000.
- Every word and the target contain only lowercase English letters.
- Every string has length at most 200.
- Two strings match only when all 26 character counts are equal.
- The input list must not be mutated.
- Duplicate matching entries remain duplicated in the output.
Examples
Input: (['listen', 'silent', 'list', 'enlist', 'silent'], 'listen')
Expected Output: ['listen', 'silent', 'enlist', 'silent']
Explanation: All exact anagrams remain in their original order, including the duplicate silent.
Input: (['', 'a', '', 'aa'], '')
Expected Output: ['', '']
Explanation: An empty target matches only empty entries.
Hints
- Use a 26-count vector as the canonical key for each string.
- Reject different lengths before counting characters.