⚡Flashcard Drill➔
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

  1. Group ideas by their suffix (the second character), storing the set of first characters in each group.
  2. Swapping the first letters of an idea from group A and an idea from group B produces a valid name only if the resulting name is not already in the input.
  3. For two groups with a and b distinct first characters and c common ones, the number of valid ordered names is 2 * (a - c) * (b - c): pick a first character from A that is not in B, one from B that is not in A, and two orderings.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems