Group strings that are anagrams
Company: J.P. Morgan
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Problem: Group anagrams
Given an array of strings `strs`, group the strings that are anagrams of each other.
Two strings are anagrams if they contain the same characters with the same multiplicities (order may differ).
### Input
- `strs`: array of strings (assume lowercase English letters unless stated otherwise).
### Output
Return a list of groups, where each group is a list of strings that are mutual anagrams.
- The order of groups does not matter.
- The order of strings inside a group does not matter.
### Constraints (typical)
- `1 ≤ len(strs) ≤ 1e5`
- `0 ≤ len(strs[i]) ≤ 100`
### Follow-ups discussed in interview
- Provide **multiple approaches**, and compare time/space tradeoffs (e.g., sorting-based key vs. character-count key).
Quick Answer: This question evaluates skills in string manipulation, grouping by character composition, and the use of hashing or sorting techniques to construct keys while reasoning about time and space trade-offs.
Given an array of strings `strs`, group the strings that are anagrams of each other.
Two strings are anagrams if they contain exactly the same characters with the same frequencies, but possibly in a different order.
Return a list of groups, where each group contains strings that are mutual anagrams.
For deterministic evaluation in this problem, follow these output-order rules:
1. Groups must appear in the order their anagram class is first seen in the input.
2. Strings inside each group must remain in their original input order.
Example: `['eat', 'tea', 'tan', 'ate']` should become `[['eat', 'tea', 'ate'], ['tan']]`.
Constraints
- 0 <= len(strs) <= 100000
- 0 <= len(strs[i]) <= 100
- Each string contains only lowercase English letters 'a' to 'z'
Examples
Input: (["eat", "tea", "tan", "ate", "nat", "bat"],)
Expected Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
Explanation: "eat", "tea", and "ate" are anagrams; "tan" and "nat" are anagrams; "bat" stands alone.
Input: (["", "b", ""],)
Expected Output: [["", ""], ["b"]]
Explanation: Both empty strings belong to the same group, and that group appears first because the first element is an empty string.
Input: ([],)
Expected Output: []
Explanation: An empty input list produces no groups.