NeetCode #169LC-2306HardArrays & Hashing
← Back to All Problems#169 · #2306 · Naming a Company(公司命名)
📌 Problem Statement & Constraints
You are given an array of distinct strings
ideas, each of length 2. A company name is formed by swapping the first letters of two ideas; it is valid if the resulting name is not in the original list. Return the number of valid names. Constraints: 2 <= ideas.length <= 5 * 10^4, ideas[i].length == 2; all ideas are distinct.💡 Core Algorithmic Approaches
- Group ideas by their suffix (the second character), storing the set of first characters in each group.
- Swapping the first letters of an idea from group
Aand an idea from groupBproduces a valid name only if the resulting name is not already in the input. - For two groups with
aandbdistinct first characters andccommon ones, the number of valid ordered names is2 * (a - c) * (b - c): pick a first character fromAthat is not inB, one fromBthat is not inA, and two orderings. - Since every idea has length 2, there are at most 26 distinct suffixes, so the O(k^2) pair loop over groups is cheap.
💻 Benchmark Python3 Implementation
class Solution:
def distinctNames(self, ideas: List[str]) -> int:
from collections import defaultdict
groups = defaultdict(set) # suffix -> set of first letters
for w in ideas:
groups[w[1]].add(w[0])
res = 0
keys = list(groups)
for i in range(len(keys)):
for j in range(i + 1, len(keys)):
a, b = groups[keys[i]], groups[keys[j]]
common = len(a & b) # first letters shared by both suffixes
res += 2 * (len(a) - common) * (len(b) - common)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + 26^2): building the groups is O(n), and the pairwise group loop is at most 325 iterations because there are only 26 possible suffixes.
💾 Space Complexity
O(n) for the groups (bounded by 26 sets of at most 26 letters).
⚠️ Interview Pitfalls & Follow-ups
- Comparing every pair of ideas: O(n^2) with n = 5 * 10^4 is far too slow; grouping by suffix collapses the problem to 26 groups.
- Forgetting the factor of 2: swapping the letters of
(a, X)and(b, Y)produces two distinct names,(b, X)and(a, Y). - Ignoring the common first letters: if a first letter appears in both groups, the swapped name would already exist, so those combinations must be excluded.
- Misreading the suffix: the suffix is the second character of each idea, and it stays in place during the swap.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.