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.
- Difficulty: Hard
- Topics: Strings, Hash Table, Bit Manipulation, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A start-up brainstorms a list of distinct single-word ideas and builds two-word company names from them like this:
- Pick two different ideas
ideaAandideaB(order matters). - Swap their first letters.
- If neither of the two new words appears in
ideas, the nameideaA 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^41 <= ideas[i].length <= 10ideas[i] consists of lowercase English lettersAll the strings in ideas are unique
Hints for Naming a Company
Hint 1
Only the first letter and the rest of the word (the suffix) matter. Group the suffixes by first letter.
Hint 2
Take ideas with first letters
a != band suffixesxandy. The swap is valid exactly whenxis not in groupbandyis not in groupa.Hint 3
So for each ordered pair of letters, the count is
(|G_a| - common) · (|G_b| - common), wherecommonis the number of suffixes in both groups. Countcommonfor 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
- Count
cnt[a], the number of ideas starting with each letter. - Map every suffix (the idea without its first letter) to a 26-bit mask of the first letters it occurs with.
- For every suffix mask and every pair of letters
a, bin that mask, incrementcommon[a][b]. - Sum
(cnt[a] - common[a][b]) · (cnt[b] - common[a][b])over all ordered pairsa != 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 ideaBandideaB ideaAare different names. - On the original problem (
nup 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 totalJava
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