##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2306.html

# 2306. Naming a Company

• Difficulty: Hard.
• Related Topics: Array, Hash Table, String, Bit Manipulation, Enumeration.
• Similar Questions: .

## Problem

You are given an array of strings ideas that represents a list of names to be used in the process of naming a company. The process of naming a company is as follows:

• Choose 2 distinct names from ideas, call them ideaA and ideaB.

• Swap the first letters of ideaA and ideaB with each other.

• If both of the new names are not found in the original ideas, then the name ideaA ideaB (the concatenation of ideaA and ideaB, separated by a space) is a valid company name.

• Otherwise, it is not a valid name.

Return the number of **distinct valid names for the company**.

Example 1:

Input: ideas = ["coffee","donuts","time","toffee"]
Output: 6
Explanation: The following selections are valid:
- ("coffee", "donuts"): The company name created is "doffee conuts".
- ("donuts", "coffee"): The company name created is "conuts doffee".
- ("donuts", "time"): The company name created is "tonuts dime".
- ("donuts", "toffee"): The company name created is "tonuts doffee".
- ("time", "donuts"): The company name created is "dime tonuts".
- ("toffee", "donuts"): The company name created is "doffee tonuts".
Therefore, there are a total of 6 distinct company names.

The following are some examples of invalid selections:
- ("coffee", "time"): The name "toffee" formed after swapping already exists in the original array.
- ("time", "toffee"): Both names are still the same after swapping and exist in the original array.
- ("coffee", "toffee"): Both names formed after swapping already exist in the original array.


Example 2:

Input: ideas = ["lack","back"]
Output: 0
Explanation: There are no valid selections. Therefore, 0 is returned.


Constraints:

• 2 <= ideas.length <= 5 * 104

• 1 <= ideas[i].length <= 10

• ideas[i] consists of lowercase English letters.

• All the strings in ideas are unique.

## Solution

• class Solution {
private long count(Map<Character, Set<String>> map, char a, char b) {
if (!map.containsKey(a) || !map.containsKey(b)) {
return 0;
}
long common = 0;
Set<String> first = map.get(a);
Set<String> second = map.get(b);
for (String c : first) {
if (second.contains(c)) {
common++;
}
}
long uniqueA = first.size() - common;
long uniqueB = second.size() - common;
return uniqueA * uniqueB * 2L;
}

public long distinctNames(String[] ideas) {
long ans = 0;
Map<Character, Set<String>> map = new HashMap<>();
for (String idea : ideas) {
char startChar = idea.charAt(0);
Set<String> values = map.getOrDefault(startChar, new HashSet<>());
map.put(startChar, values);
}
for (int i = 0; i <= 26; i++) {
for (int j = i + 1; j <= 26; j++) {
long unique = count(map, (char) (i + 'a'), (char) (j + 'a'));
ans += unique;
}
}
return ans;
}
}

• class Solution {
public:
long long distinctNames(vector<string>& ideas) {
unordered_set<string> s(ideas.begin(), ideas.end());
vector<vector<int>> f(26, vector<int>(26));
for (auto v : ideas) {
int i = v - 'a';
for (int j = 0; j < 26; ++j) {
v = j + 'a';
if (!s.count(v)) {
++f[i][j];
}
}
}
long long ans = 0;
for (auto v : ideas) {
int i = v - 'a';
for (int j = 0; j < 26; ++j) {
v = j + 'a';
if (!s.count(v)) {
ans += f[j][i];
}
}
}
return ans;
}
};

• class Solution:
def distinctNames(self, ideas: List[str]) -> int:
s = set(ideas)
f = [ * 26 for _ in range(26)]
for v in ideas:
i = ord(v) - ord('a')
t = list(v)
for j in range(26):
t = chr(ord('a') + j)
if ''.join(t) not in s:
f[i][j] += 1
ans = 0
for v in ideas:
i = ord(v) - ord('a')
t = list(v)
for j in range(26):
t = chr(ord('a') + j)
if ''.join(t) not in s:
ans += f[j][i]
return ans

############

# 2306. Naming a Company
# https://leetcode.com/problems/naming-a-company/

class Solution:
def distinctNames(self, ideas: List[str]) -> int:
n = len(ideas)
counts = [ * 26 for _ in range(26)]
seen = set(ideas)
orda = ord("a")

for idea in ideas:
for c in range(26):
if chr(orda + c) + idea[1:] not in seen:
counts[ord(idea) - orda][c] += 1

res = 0

for idea in ideas:
for c in range(26):
if chr(orda + c) + idea[1:] not in seen:
res += counts[c][ord(idea) - orda]

return res



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).