Naming a Company

hard hash set grouping

Problem

You are given a list of distinct lowercase idea names. To build a company name you pick two different ideas, swap their first letters, and join the two swapped words with a space. The name is valid only if neither swapped word already appears in the original list. The two ideas are ordered, so "A B" and "B A" count separately.

Return the number of distinct valid company names you can form.

Inputideas = ["coffee","donuts","time","toffee"]

Output6

"coffee donuts", "donuts coffee", "time donuts", "donuts time", "toffee donuts", "donuts toffee" all work; swapping "coffee" with "toffee" fails because both swapped words already exist.

ideas (comma-separated, distinct lowercase words)

def distinct_names(ideas):
    groups = [set() for _ in range(26)]
    for name in ideas:
        groups[ord(name[0]) - ord('a')].add(name[1:])
    total = 0
    for a in range(26):
        for b in range(a + 1, 26):
            common = len(groups[a] & groups[b])
            total += 2 * (len(groups[a]) - common) * (len(groups[b]) - common)
    return total

function distinctNames(ideas) {
  const groups = Array.from({ length: 26 }, () => new Set());
  for (const name of ideas) {
    groups[name.charCodeAt(0) - 97].add(name.slice(1));
  }
  let total = 0;
  for (let a = 0; a < 26; a++) {
    for (let b = a + 1; b < 26; b++) {
      let common = 0;
      for (const s of groups[a]) if (groups[b].has(s)) common++;
      total += 2 * (groups[a].size - common) * (groups[b].size - common);
    }
  }
  return total;
}

long distinctNames(String[] ideas) {
    Set<String>[] groups = new HashSet[26];
    for (int i = 0; i < 26; i++) groups[i] = new HashSet<>();
    for (String name : ideas) {
        groups[name.charAt(0) - 'a'].add(name.substring(1));
    }
    long total = 0;
    for (int a = 0; a < 26; a++) {
        for (int b = a + 1; b < 26; b++) {
            int common = 0;
            for (String s : groups[a]) if (groups[b].contains(s)) common++;
            total += 2L * (groups[a].size() - common) * (groups[b].size() - common);
        }
    }
    return total;
}

long long distinctNames(vector<string>& ideas) {
    unordered_set<string> groups[26];
    for (auto& name : ideas) {
        groups[name[0] - 'a'].insert(name.substr(1));
    }
    long long total = 0;
    for (int a = 0; a < 26; a++) {
        for (int b = a + 1; b < 26; b++) {
            int common = 0;
            for (auto& s : groups[a]) if (groups[b].count(s)) common++;
            long long sa = (long long) groups[a].size() - common;
            total += 2 * sa * ((long long) groups[b].size() - common);
        }
    }
    return total;
}

Explanation

The key insight is that whether a swap works depends only on first letters and suffixes. Swapping ideas x + S and y + T (first letter plus suffix) produces y + S and x + T. The swap fails exactly when suffix S already exists under letter y, or suffix T already exists under letter x.

So we bucket every idea's suffix into one of 26 hash sets, keyed by its first letter. Two ideas with the same first letter can never pair: swapping identical letters reproduces both original words, which are in the list.

For a pair of distinct letters a and b, let m be the size of the intersection of their suffix sets. A suffix appearing in both groups is mutually blocked — it can pair in neither direction. Every other combination works, giving (|A| − m) · (|B| − m) unordered pairs, doubled because "A B" and "B A" are different company names.

With ideas = ["coffee","donuts","time","toffee"], the groups are c → {offee}, d → {onuts}, t → {ime, offee}. Pair (c,d): no shared suffix → 1·1·2 = 2. Pair (c,t): "offee" is shared, so (1−1)·(2−1)·2 = 0. Pair (d,t): no shared suffix → 1·2·2 = 4. Total = 6.

Why this is fast: instead of testing all O(n²) idea pairs (n up to 5·10⁴), we test only 26·25/2 = 325 letter pairs. Each intersection is computed with hash lookups, scanning each group a constant number of times (at most 25 — once per partner letter), so the total work is about O(26 · n) suffix probes.

Time: O(26 · n) Space: O(n)