Back to solutions

Naming a Company

HardArrays

Count valid company names from swapping first letters of two ideas.

Open problem
Constraints
  • 1 <= n <= 10^5
  • words are distinct lowercase

Group suffixes by first letter

Time O(26 * total suffixes)Space O(total suffixes)

Group every word's suffix (everything after the first letter) by its first letter into 26 buckets. For two first letters a and b, a swap is valid only when the suffix does not already exist in the other bucket. So suffixes shared by both buckets are unusable; only the exclusive suffixes pair up. For each unordered letter pair, the count is 2 * (exclusive in a) * (exclusive in b).

Key terms
suffix:
The part of a word after removing its first character.
common suffix:
A suffix present under both first letters; swapping it produces an existing word, so it is invalid.
ordered pair:
Both orders (a,b) and (b,a) count, hence the factor of 2.
long long distinctNames(vector<string>& ideas) {
    unordered_set<string> sets[26];
    for (auto& w : ideas) sets[w[0] - 'a'].insert(w.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& suf : sets[a]) if (sets[b].count(suf)) common++;
            long long onlyA = sets[a].size() - common, onlyB = sets[b].size() - common;
            total += 2 * onlyA * onlyB;
        }
    return total;
}
Step by step
  1. Bucket each suffix under its word's first letter (26 sets).
  2. For each pair of letters (a, b), count suffixes common to both buckets.
  3. Valid combinations use only suffixes exclusive to each: (|a| - common) and (|b| - common).
  4. Add 2 * onlyA * onlyB to the total for both orders.