Naming a Company

How it works

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.

Steps

1. Build a map from each suffix to a boolean array of size 26, indicating which first letters it appears with.
2. Initialize a 26x26 count matrix to zero.
3. 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).
4. Return 2 times the result (for both orderings).

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.

Things to watch for

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.

from typing import List
from collections import defaultdict

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

class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        unordered_map<string, array<bool, 26>> mp;
        long long count[26][26] = {};
        long long res = 0;

        for (const string& s : ideas) {
            int firstChar = s[0] - 'a';
            string suffix = s.substr(1);
            mp[suffix][firstChar] = true;
        }

        for (auto& [suffix, arr] : mp) {
            for (int i = 0; i < 26; i++) {
                if (arr[i]) {
                    for (int j = 0; j < 26; j++) {
                        if (!arr[j]) {
                            count[i][j]++;
                            res += count[j][i];
                        }
                    }
                }
            }
        }
        return 2 * res;
    }
};