Design O(nm) grouping of rearranged strings
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an array of strings, group together words that are permutations of the same characters. Provide a baseline solution that sorts each word (O(n · m log m), where n is the number of words and m is max word length). Then, under assumptions such as inputs consist only of lowercase 'a'–'z', design an O(n · m) solution using character-frequency hashing. Specify how you construct a stable key (e.g., serialized counts), handle collisions, and analyze time and space trade-offs versus sorting.
Quick Answer: This question evaluates a candidate's understanding of string manipulation, hashing and frequency-count techniques, algorithmic optimization, and time/space complexity analysis when grouping anagrams.
Given an array of strings `words`, group together all words that are permutations (anagrams) of one another and return the list of groups.
A baseline approach sorts each word to form a canonical key, costing O(n·m log m) where n is the number of words and m is the maximum word length. Under the assumption that every word consists only of lowercase letters 'a'–'z', you can do better: build a stable key from a 26-element character-frequency count instead of sorting, achieving O(n·m) time.
**Key construction:** For each word, compute the count of each of the 26 letters and serialize those counts into a string key (e.g. join the counts with a separator like `'#'`). Two words are anagrams iff their count vectors are identical, so they map to the same key. Using a non-numeric separator between counts prevents collisions between counts of different magnitude (e.g. `[1,12]` vs `[11,2]`).
Return the groups as a list of lists. For deterministic output: groups appear in the order their first member was encountered in the input, and the words inside each group are sorted in ascending (lexicographic) order. The original word strings are preserved (not the sorted/canonical form).
Constraints
- 1 <= n <= 10^4 (number of words); the array may also be empty.
- 0 <= len(word) <= 100
- Each word consists only of lowercase English letters 'a'–'z' (the empty string is allowed).
- Total characters across all words fit comfortably in memory.
Examples
Input: (["eat", "tea", "tan", "ate", "nat", "bat"],)
Expected Output: [['ate', 'eat', 'tea'], ['nat', 'tan'], ['bat']]
Explanation: eat/tea/ate share counts {a,e,t}; tan/nat share {a,n,t}; bat is alone. Groups appear in first-seen order; each group's words are sorted.
Input: ([""],)
Expected Output: [['']]
Explanation: A single empty string forms one group containing just the empty string (its count vector is all zeros).
Hints
- Two words are anagrams iff they have the same multiset of characters. Avoid sorting each word — instead derive a key directly from character counts.
- Use a fixed-size array of 26 integers (one per letter) as the count vector, then serialize it into a hashable key.
- Serialize counts with a separator between numbers (e.g. join with '#') so that [1, 12] and [11, 2] don't collide into the same string.
- A dictionary preserves insertion order in modern Python, giving deterministic first-seen group ordering; sort each group's words before returning for a stable result.