Quick Overview

Group anagrams without sorting each word's characters, preserving repeated words and reasoning about frequency signatures and overflow-prone encodings.

Group Anagrams Without Sorted Character Signatures

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

Given an array of strings, group all words that are anagrams of one another. Two words are anagrams when every character occurs the same number of times in both words. Return groups that contain every input occurrence exactly once. Repeated identical words remain repeated occurrences in their group. For deterministic output presentation, list groups by the earliest input occurrence of any member. Within each group, list word occurrences in their original input order. This presentation rule does not change which words belong together. ### Input and Output - Input: an array of strings over lowercase English letters `a` through `z`. For this practice version, an empty word is allowed and all empty words belong in one group. An empty input array returns no groups. - Output: an array of anagram groups in the presentation order described above. Do not create an anagram signature by sorting each word's characters. The source explicitly rules out that per-word sorting approach. The output-order convention does not relax this restriction. ### Example ```text words = ["eat", "tea", "bat", "ate", "bat"] answer = [["eat", "tea", "ate"], ["bat", "bat"]] ``` The `eat` group appears first because its first member is the first input word. Within each group, words retain their input order. The source also asks about overflow and collision risks of fixed-width prime-product signatures; that discussion is separate from the returned grouping.

Overview: Group anagrams without sorting each word's characters, preserving repeated words and reasoning about frequency signatures and overflow-prone encodings.

Read the full Amazon Software Engineer interview experience this question came from

Given an array of strings, group all words that are anagrams of one another. Two words are anagrams when every character occurs the same number of times in both words. Return groups that contain every input occurrence exactly once. Repeated identical words remain repeated occurrences in their group. For deterministic output presentation, list groups by the earliest input occurrence of any member. Within each group, list word occurrences in their original input order. This presentation rule does not change which words belong together. ### Input and Output - Input: an array of strings over lowercase English letters `a` through `z`. For this practice version, an empty word is allowed and all empty words belong in one group. An empty input array returns no groups. - Output: an array of anagram groups in the presentation order described above. Do not create an anagram signature by sorting each word's characters. The source explicitly rules out that per-word sorting approach. The output-order convention does not relax this restriction. ### Example ```text words = ["eat", "tea", "bat", "ate", "bat"] answer = [["eat", "tea", "ate"], ["bat", "bat"]] ``` The `eat` group appears first because its first member is the first input word. Within each group, words retain their input order. The source also asks about overflow and collision risks of fixed-width prime-product signatures; that discussion is separate from the returned grouping.

Constraints

  • words is a finite array of lowercase a-z strings; empty strings and an empty array are allowed.
  • Return every occurrence exactly once, with groups by first input occurrence and members in input order.
  • Do not sort each word to form its anagram signature.

Examples

Input: (['eat', 'tea', 'bat', 'ate', 'bat'],)

Expected Output: [['eat', 'tea', 'ate'], ['bat', 'bat']]

Explanation: Interleaved groups retain first-occurrence order and duplicate words.

Input: (['ab', 'cd', 'ba', 'dc', 'ab'],)

Expected Output: [['ab', 'ba', 'ab'], ['cd', 'dc']]

Explanation: Two groups preserve each member occurrence in input order.

Hints

  1. Words belong together only when each lowercase letter has the same multiplicity.
  2. Preserve the order in which a group first appears and the order of its members.

Loading coding console...

Show the approach

Approach

Count the 26 lowercase letters of each word. A count vector identifies exactly one anagram class, including the empty word. Store the index of the first group for each vector, and append each word as it is read. New groups are created on first occurrence, so group order and member order match the required presentation. Every input occurrence is appended once. The count key has explicit separators or tuple entries, so distinct count vectors cannot collide by concatenation, and no word is character-sorted or encoded as a fixed-width prime product.

Time complexity:
O(L + 26n), where n is the number of words and L is their total length.
Space complexity:
O(L + 26n) including returned groups and count keys.