Group a list of words so that words which are anagrams of each other end up together. What is your key, and what does it cost?

What the key has to be

The entire problem is one sentence: find a function from a word to a value that is equal for two words exactly when they are anagrams. Once you have that, the answer is one pass, inserting each word into a map keyed by that value and returning the map's values. Everything else is a choice about which canonical form to compute.

Saying it that way first is worth doing, because it makes the two candidate answers obviously two instances of the same idea rather than two tricks. It also makes the failure mode legible in advance: any key that can be equal for two non-anagrams is broken, and it will be broken silently, merging groups that should be separate.

Sorted letters against counted letters

The first key is the word's characters sorted. It is trivially canonical, since two words are anagrams precisely when their sorted forms are identical, and it costs O of k log k per word for a word of length k. For short words this is the right answer, and the reason to prefer it in an interview is that it is impossible to get wrong.

The second key is a vector of counts, one slot per letter of the alphabet. Two words are anagrams exactly when their count vectors are equal, so it is also canonical, and it costs O of k to build plus O of A to serialise, where A is the alphabet size. For a fixed twenty-six-letter alphabet and long words this beats sorting, and the crossover is where k log k exceeds k plus A, which for realistic words is somewhere quite large.

State the crossover as a comparison rather than picking a winner. The counting key wins on long words over a small alphabet; the sorting key wins on short words, and on any alphabet large enough that a full count vector is mostly zeros.

Where the counting key goes wrong without a separator

The counting key has to become something a hash map can use, and the tempting move is to concatenate the counts into a string. That is where the bug is, and it survives most test suites.

Consider a word with eleven a's and one b, and a word with one a and eleven b's. The first has counts eleven, one, then twenty-four zeros; the second has one, eleven, then twenty-four zeros. Concatenated without separators, the first yields the characters 11 followed by 1, and the second yields 1 followed by 11. Both are 111, followed in each case by twenty-four 0s. The two words are not anagrams — one is mostly a's and the other mostly b's — and they receive the same key, so they are merged into one group.

The fix is one character. Emit a delimiter after every count, or emit a fixed-width field, and the ambiguity disappears because the boundaries between counts become recoverable. This is the same class of defect as building a cache key by concatenating fields without a separator, where two different field pairs collide, and the same fix applies.

Arrays are not map keys

If you keep the counts as an int[] and use it directly as a map key in Java, every insertion creates a new group. Arrays inherit hashCode and equals from Object, so they are compared by identity, and two arrays holding identical contents are never equal. Nothing warns you; the code compiles and returns one group per word.

The options are to serialise the counts to a string, as above, or to wrap them in a type with value semantics, or in this specific case to reuse a single scratch array and turn it into a string before the next word. A candidate who reaches for a scratch array should be able to say why they clear it between words rather than allocating fresh, and why the string has to be built before the array is reused.

Map<String, List<String>> groupAnagrams(String[] words) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String word : words) {
        int[] counts = new int[26];
        for (int i = 0; i < word.length(); i++) counts[word.charAt(i) - 'a']++;

        StringBuilder key = new StringBuilder();
        for (int count : counts) key.append(count).append('#');   // delimiter, not optional

        groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(word);
    }
    return groups;
}

Overall this is O of n times open bracket k plus A close bracket time for n words, and O of the total input size in space, because every word is retained in some group. If only the group sizes are wanted, the words themselves need not be stored, and saying so is a cheap way to show you have separated the algorithm from the output format.

The assumption in the twenty-six

The fixed array of twenty-six assumes lower-case unaccented Latin letters, and the interviewer usually planted it by giving you exactly that in the example. Ask.

If case is insignificant, case-fold before counting, and note that folding is not always a per-character operation across languages. If the input is arbitrary Unicode, the count vector cannot be a fixed array and becomes a map, at which point the sorting key or a sorted list of code-point-count pairs is simpler. And if accents are in play, two strings that render identically may differ in their code points, because a letter with a diacritic can be encoded as one code point or as a base letter followed by a combining mark. Normalising to a single form before computing any key is a prerequisite, not a refinement, and it is the kind of detail that distinguishes a candidate who has processed real text from one who has only processed test fixtures.