2306.Naming a Company
===

###### tags: `Hard`,`Array`,`String`,`Hash Table`,`Bit Manipulation`

[2306. Naming a Company](https://leetcode.com/problems/naming-a-company/)

### 題目描述

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 * 10^4^
* 1 <= `ideas[i].length` <= 10
* `ideas[i]` consists of lowercase English letters.
* All the strings in `ideas` are **unique**.

### 解答
#### C++

class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        unordered_set<string> groups[26];
        for (const auto& idea : ideas) {
            groups[idea[0] - 'a'].insert(idea.substr(1));
        }
        long long ans = 0;
        for (int i = 0; i < 25; i++) {
            for (int j = i + 1; j < 26; j++) {
                long long overlap = 0;
                for (const auto& word: groups[i]) {
                    overlap += groups[j].count(word);
                }
                ans += 2 * (groups[i].size() - overlap) * (groups[j].size() - overlap);
            }
        }
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Thu, Feb 9, 2023]

##### 思路:
1. 選兩個idea, 交換第一個char, 若交換後的單字沒出現在原本的輸入即為合法名字, 找出所有合法名字的數量
2. 交換後若有跟輸入重複者, 代表兩個idea第二個字元後開始後綴一樣
3. 可以第一個字元做分組, 每兩組比較個數, 扣除一樣的後綴數量相乘即此兩組可形成的合法數量

Time: $O(n*m)$ `m`為平均idea長度, 共有`26*25/2=325`個pair group比較, 每個pair group比較花$O(n*m)$
Extra Space: $O(n*m)$

> [name=XD] [time= Feb 9, 2023]

#### Python

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        groups = [set() for _ in range(26)]
        for idea in ideas:
            groups[ord(idea[0]) - ord('a')].add(idea[1:])
        ans = 0
        for i in range(25):
            for j in range(i + 1, 26):
                overlap = len(groups[i] & groups[j])
                ans += 2 * (len(groups[i]) - overlap) * (len(groups[j]) - overlap)
        return ans

> [name=Yen-Chi Chen][time=Thu, Feb 9, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)