2306. Naming a Company - Explanation

1. Brute Force

Intuition

To form a valid company name, we pick two distinct ideas and swap their first letters. The resulting two names must both be new (not in the original list). A straightforward approach checks every pair of ideas, performs the swap, and verifies that neither swapped name exists in the original set. We track valid combinations in a set to avoid counting duplicates.

This works but is slow because we examine O(n^2) pairs, and string operations add additional cost.

Algorithm

Store all ideas in a set for O(1) lookup.
For each pair of ideas (i, j) where i < j:
- Swap the first letters to create two new names A and B.
- If neither A nor B exists in the original set, add both orderings to the res set.
Return the size of the res set.

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        n = len(ideas)
        res = set()
        ideasSet = set(ideas)

        for i in range(n):
            for j in range(i + 1, n):
                A, B = ideas[j][0] + ideas[i][1:], ideas[i][0] + ideas[j][1:]
                if A not in ideasSet and B not in ideasSet:
                    res.add(A + ' ' + B)
                    res.add(B + ' ' + A)

        return len(res)

Time & Space Complexity

Time complexity: $O(m * n ^ 2)$
Space complexity: $O(m * n ^ 2)$

Where $n$ is the size of the array $ideas$ and $m$ is the average length of the strings.

2. Group By First Letter (Hash Map)

Intuition

The key insight is that swapping first letters only matters between ideas that start with different letters. If two ideas share the same first letter, swapping produces the same names back.

Group ideas by their first letter, storing only the suffixes (the part after the first character). For two groups with different first letters, a swap is valid if the suffix appears in exactly one group (not both). If a suffix appears in both groups, swapping would produce an existing name.

For groups A and B, count how many suffixes are shared (the intersection). The number of valid pairs is (size of A minus intersection) times (size of B minus intersection).

Algorithm

Build a map where each key is a first letter and each value is a set of suffixes starting with that letter.
For each pair of distinct first letters (char1, char2):
- Count how many suffixes appear in both groups (intersect).
- Compute distinct1 = size of group char1 minus intersect.
- Compute distinct2 = size of group char2 minus intersect.
- Add distinct1 * distinct2 to the result.
Return the total result.

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        wordMap = collections.defaultdict(set)
        for w in ideas:
            wordMap[w[0]].add(w[1:])

        res = 0
        for char1 in wordMap:
            for char2 in wordMap:
                if char1 == char2:
                    continue

                intersect = sum(1 for w in wordMap[char1] if w in wordMap[char2])
                distinct1 = len(wordMap[char1]) - intersect
                distinct2 = len(wordMap[char2]) - intersect
                res += distinct1 * distinct2

        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $n$ is the size of the array $ideas$ and $m$ is the average length of the strings.

3. Group By First Letter (Array)

Intuition

This approach is the same as the hash map solution, but uses a fixed-size array of 26 sets instead of a hash map. Since we only deal with lowercase letters, indexing by (character minus 'a') gives us direct array access, which can be slightly faster.

We also optimize by only iterating over pairs (i, j) where i < j, then multiplying the result by 2 to account for both orderings.

Algorithm

Create an array of 26 sets, one for each letter. Store suffixes in the set corresponding to each idea's first letter.
For each pair of indices (i, j) where i < j:
- Count the intersect of suffixes between groups i and j.
- Compute the product of non-overlapping suffix counts.
- Add 2 times this product to the result (for both orderings).
Return the total result.

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        suffixes = [set() for _ in range(26)]
        for w in ideas:
            suffixes[ord(w[0]) - ord('a')].add(w[1:])

        res = 0
        for i in range(26):
            for j in range(i + 1, 26):
                intersect = len(suffixes[i] & suffixes[j])
                res += 2 * (len(suffixes[i]) - intersect) * (len(suffixes[j]) - intersect)

        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $n$ is the size of the array $ideas$ and $m$ is the average length of the strings.

4. Counting

Intuition

Instead of computing intersections for each pair of letters, we can build a count matrix incrementally. For each suffix, we know which first letters it appears with. We process suffixes one by one and maintain count[i][j], which tracks how many suffixes have appeared with letter i but not with letter j.

When we encounter a suffix that appears with letter i but not letter j, any previous suffix that appeared with letter j but not letter i forms a valid pair. We look up count[j][i] to find how many such suffixes exist.

Algorithm

Build a map from each suffix to a boolean array of size 26, indicating which first letters it appears with.
Initialize a 26x26 count matrix to zero.
For each suffix and its boolean array:
- For each letter i where the suffix appears:
  - For each letter j where the suffix does not appear:
    - Increment count[i][j].
    - Add count[j][i] to the result (these are valid pairings).
Return 2 times the result (for both orderings).

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        mp = defaultdict(lambda: [False] * 26)
        count = [[0] * 26 for _ in range(26)]
        res = 0

        for s in ideas:
            first_char = ord(s[0]) - ord('a')
            suffix = s[1:]
            mp[suffix][first_char] = True

        for suffix, arr in mp.items():
            for i in range(26):
                if arr[i]:
                    for j in range(26):
                        if not arr[j]:
                            count[i][j] += 1
                            res += count[j][i]

        return 2 * res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $n$ is the size of the array $ideas$ and $m$ is the average length of the strings.

Common Pitfalls

Checking Both Swapped Names

A valid company name requires that both swapped names are new. Some solutions only check if one of the swapped names exists in the original set, forgetting that both must be absent. If either swapped name already exists as an original idea, the pair is invalid.

Counting Pairs vs Ordered Names

The problem asks for distinct company names, which are ordered pairs (first name + second name). After finding a valid swap between two ideas, you must count both orderings. Forgetting to multiply by 2 or add both orderings leads to answers that are half the correct value.

Same First Letter Produces No New Names

Swapping first letters between two ideas that start with the same letter produces the original names back. Solutions that do not skip pairs with identical first letters waste computation and may produce incorrect intersection counts in the optimized approaches.

Off-by-One in Suffix Extraction

When grouping by first letter, the suffix is everything after the first character. Using s[1:] correctly extracts the suffix, but some implementations accidentally include the first character or miss the last character due to incorrect slicing, causing lookups to fail.

Integer Overflow in Pair Counting

With up to 50,000 ideas, the number of valid pairs can exceed 32-bit integer limits. The product of two group sizes (each up to 50,000) requires 64-bit arithmetic. Using int instead of long in languages like Java causes overflow and wrong answers.