Naming a Company

Hard
1259.

Naming a Company

Naming a Company is a hard coding problem on strings, hash table and bit manipulation, asked in Amazon and Google interviews.

A start-up brainstorms a list of distinct single-word ideas and builds two-word company names from them like this:

  1. Pick two different ideas ideaA and ideaB (order matters).
  2. Swap their first letters.
  3. If neither of the two new words appears in ideas, the name ideaA ideaB (the two new words joined by a space) is valid.

Return the number of distinct valid company names.

CodeKairo bound: at most 40,000 ideas here, so the answer always fits in a 32-bit integer.

Example 1

Input
ideas = ["code","kairo","duel","kata"]
Output
10
Explanation
For example `code` + `kairo` gives `kode cairo`, valid because neither word is an idea. Only pairs that share a suffix such as `kata`/`kairo` (both starting with `k`) fail.

Example 2

Input
ideas = ["lack","back"]
Output
0
Explanation
Swapping gives back the same two words, which are ideas.

Example 3

Input
ideas = ["bat","cat","rat","bee","see"]
Output
4

Constraints

  • 2 <= ideas.length <= 4 * 10^4
  • 1 <= ideas[i].length <= 10
  • ideas[i] consists of lowercase English letters
  • All the strings in ideas are unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} ideas
 * @return {number}
 */
var distinctNames = function(ideas) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Naming a Company — Solution in Python, Java & C++

Naming a Company solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on strings and hash table.

Naming a Company is a hard coding problem on strings, hash table and bit manipulation, asked in Amazon and Google interviews.

Problem statement

A start-up brainstorms a list of distinct single-word ideas and builds two-word company names from them like this:

  1. Pick two different ideas ideaA and ideaB (order matters).
  2. Swap their first letters.
  3. If neither of the two new words appears in ideas, the name ideaA ideaB (the two new words joined by a space) is valid.

Return the number of distinct valid company names.

CodeKairo bound: at most 40,000 ideas here, so the answer always fits in a 32-bit integer.

Example 1

Input: ideas = ["code","kairo","duel","kata"]
Output: 10
Explanation: For example `code` + `kairo` gives `kode cairo`, valid because neither word is an idea. Only pairs that share a suffix such as `kata`/`kairo` (both starting with `k`) fail.

Example 2

Input: ideas = ["lack","back"]
Output: 0
Explanation: Swapping gives back the same two words, which are ideas.

Example 3

Input: ideas = ["bat","cat","rat","bee","see"]
Output: 4

Constraints

  • 2 <= ideas.length <= 4 * 10^4
  • 1 <= ideas[i].length <= 10
  • ideas[i] consists of lowercase English letters
  • All the strings in ideas are unique

Hints for Naming a Company

  1. Hint 1

    Only the first letter and the rest of the word (the suffix) matter. Group the suffixes by first letter.

  2. Hint 2

    Take ideas with first letters a != b and suffixes x and y. The swap is valid exactly when x is not in group b and y is not in group a.

  3. Hint 3

    So for each ordered pair of letters, the count is (|G_a| - common) · (|G_b| - common), where common is the number of suffixes in both groups. Count common for all 26 × 26 pairs at once by recording, for each suffix, the set of first letters it appears with.

How to solve Naming a Company

A swap between an idea in group a and one in group b (grouped by first letter) works iff each suffix is missing from the other group. Same-letter pairs never work. So the answer is a sum over 26 × 26 letter pairs of products of "suffixes not shared" counts.

Approach

  1. Count cnt[a], the number of ideas starting with each letter.
  2. Map every suffix (the idea without its first letter) to a 26-bit mask of the first letters it occurs with.
  3. For every suffix mask and every pair of letters a, b in that mask, increment common[a][b].
  4. Sum (cnt[a] - common[a][b]) · (cnt[b] - common[a][b]) over all ordered pairs a != b.

Why it works

Picking a·x and b·y yields the words b·x and a·y; they are new iff x ∉ G_b and y ∉ G_a. The two conditions are independent, so the number of valid pairs for letters (a, b) is the product of |G_a \ G_b| and |G_b \ G_a|, and |G_a \ G_b| = cnt[a] - common[a][b]. For a == b the swap returns the original ideas, so those pairs contribute nothing. Different idea pairs give different names, so counting pairs counts names.

Complexity

  • Time — O(n · L + 26^2) — plus the squared size of each suffix's letter set, at most 26 · n in total
  • Space — O(n · L)

Pitfalls

  • Checking every pair of ideas is O(n^2) — 1.6 · 10^9 checks at the upper bound.
  • The order of the pair matters: ideaA ideaB and ideaB ideaA are different names.
  • On the original problem (n up to 5 · 10^4) the count needs 64 bits; it fits here only because of the tighter bound.

Reference solution

Python

from typing import List

def distinctNames(ideas: List[str]) -> int:
    cnt = [0] * 26
    masks = {}
    for w in ideas:
        c = ord(w[0]) - 97
        cnt[c] += 1
        suf = w[1:]
        masks[suf] = masks.get(suf, 0) | (1 << c)
    common = [[0] * 26 for _ in range(26)]
    for m in masks.values():
        bits = [b for b in range(26) if (m >> b) & 1]
        for a in bits:
            row = common[a]
            for b in bits:
                row[b] += 1
    total = 0
    for a in range(26):
        for b in range(26):
            if a != b:
                total += (cnt[a] - common[a][b]) * (cnt[b] - common[a][b])
    return total

Java

public static int distinctNames(String[] ideas) {
    long[] cnt = new long[26];
    Map<String, Integer> masks = new HashMap<>();
    for (String w : ideas) {
        int c = w.charAt(0) - 'a';
        cnt[c]++;
        masks.merge(w.substring(1), 1 << c, (x, y) -> x | y);
    }
    long[][] common = new long[26][26];
    for (int m : masks.values()) {
        for (int a = 0; a < 26; a++) {
            if (((m >> a) & 1) == 0) continue;
            for (int b = 0; b < 26; b++) if (((m >> b) & 1) != 0) common[a][b]++;
        }
    }
    long total = 0;
    for (int a = 0; a < 26; a++) {
        for (int b = 0; b < 26; b++) {
            if (a != b) total += (cnt[a] - common[a][b]) * (cnt[b] - common[a][b]);
        }
    }
    return (int) total;
}

C++

int distinctNames(vector<string>& ideas) {
    long long cnt[26] = {0};
    unordered_map<string, int> masks;
    for (const string& w : ideas) {
        int c = w[0] - 'a';
        cnt[c]++;
        masks[w.substr(1)] |= 1 << c;
    }
    vector<vector<long long>> common(26, vector<long long>(26, 0));
    for (auto& kv : masks) {
        int m = kv.second;
        for (int a = 0; a < 26; a++) {
            if (!((m >> a) & 1)) continue;
            for (int b = 0; b < 26; b++) if ((m >> b) & 1) common[a][b]++;
        }
    }
    long long total = 0;
    for (int a = 0; a < 26; a++) {
        for (int b = 0; b < 26; b++) {
            if (a != b) total += (cnt[a] - common[a][b]) * (cnt[b] - common[a][b]);
        }
    }
    return (int)total;
}

JavaScript

var distinctNames = function(ideas) {
    var cnt = new Array(26).fill(0);
    var masks = new Map();
    for (var i = 0; i < ideas.length; i++) {
        var w = ideas[i];
        var c = w.charCodeAt(0) - 97;
        cnt[c]++;
        var suf = w.substring(1);
        var prev = masks.get(suf);
        masks.set(suf, (prev === undefined ? 0 : prev) | (1 << c));
    }
    var common = [];
    for (var a = 0; a < 26; a++) common.push(new Array(26).fill(0));
    masks.forEach(function(m) {
        for (var x = 0; x < 26; x++) {
            if (((m >> x) & 1) === 0) continue;
            for (var y = 0; y < 26; y++) if ((m >> y) & 1) common[x][y]++;
        }
    });
    var total = 0;
    for (var p = 0; p < 26; p++) {
        for (var q = 0; q < 26; q++) {
            if (p !== q) total += (cnt[p] - common[p][q]) * (cnt[q] - common[p][q]);
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets