Group Anagrams

Given an array of lowercase strings strs, group together the strings that are anagrams of one another.

Under this judge contract, keep the output deterministic:

• preserve the order in which groups first appear in the input;
• preserve the original input order inside each group.

Input / output

• Input: strs: string[]
• Output: string[][]

Examples

1. strs = ["eat","tea","tan","ate","nat","bat"] returns [["eat","tea","ate"],["tan","nat"],["bat"]]. The first group is created by "eat", then "tan", then "bat".
2. strs = [""] returns [[""]]. The empty string forms a valid one-word anagram group.
3. strs = ["abc","bca","cab","foo","ofo"] returns [["abc","bca","cab"],["foo","ofo"]]. Each bucket contains exactly the words with matching character counts.

Constraints

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] contains only lowercase English letters

Edge cases

• Empty strings can appear.
• Duplicate words should stay duplicated in the same group.
• Single-word groups are valid.

Target complexity

• Aim for O(n * k) time, where k is the maximum word length.
• Aim for O(n * k) space for the hash buckets and stored output.

Hints

1. Two words are anagrams exactly when every letter count matches.
2. Build a canonical key from the 26 lowercase letter frequencies instead of sorting every string.

Follow-up What trade-off do you make if you sort each string to build the key instead of counting letters?