Naming a Company

Naming a Company

What is this problem about?

The Naming a Company problem gives you a list of existing company names (strings). You want to create new names by swapping the first letters of two existing names. The new pair of names is valid if neither name already exists in the original list. Count all valid new name pairs you can form. This hard Naming a Company coding problem uses suffix grouping with set intersection to efficiently count valid swaps.

Why is this asked in interviews?

Google asks this hard problem because the naive O(n²) approach — trying all pairs and checking membership — is too slow. The efficient solution groups words by their suffix (everything after the first letter), then for each pair of distinct suffixes, counts valid first-letter swap combinations using set intersection. The array, hash table, enumeration, string, and bit manipulation interview pattern is exercised here.

Algorithmic pattern used

Suffix grouping + set intersection counting. Group words by their suffix (word[1:]). For each suffix group, store the set of first letters used. For every pair of suffix groups (A, B), the number of valid first-letter swaps = (|A| - |intersection(A,B)|) * (|B| - |intersection(A,B)|). Each such pair contributes 2× valid name pairs (A→B and B→A swap). Sum all contributions.

Example explanation

Words: ["coffee","donuts","time","toffee"]. Groups: "offee"→{c,t}, "onuts"→{d}, "ime"→{t}. Pair ("offee", "onuts"): intersection={}, valid = (2-0)(1-0) = 2. Total so far = 22=4. Pair ("offee", "ime"): intersection={t}, valid = (2-1)(1-1) = 0. Pair ("onuts", "ime"): intersection={}, valid = 11=1. Total contribution = 2. Grand total = 4+2=6.

Common mistakes candidates make

• Brute-force O(n²) all-pairs checking (TLE on large inputs).
• Not grouping by suffix (attempting to group by first letter instead).
• Forgetting to multiply by 2 for both directions of a swap.
• Counting intersection incorrectly (intersecting full word sets vs first-letter sets).

Interview preparation tip

Hard enumeration problems often require a key transformation that reduces the problem size. Here, grouping by suffix reduces an O(n²) check to O(26²) pair evaluations (at most 26 distinct first letters). Recognize "swap one attribute between two entities" problems — they commonly group by the unchanged attribute and enumerate changed attributes. This suffix-grouping pattern is reusable across string and company-name style problems.