[LeetCode] Naming a Company

2306. 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:

  1. Choose 2 distinct names from ideas, call them ideaA and ideaB.
  2. Swap the first letters of ideaA and ideaB with each other.
  3. 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.
  4. Otherwise, it is not a valid name.

Return the number of distinct valid names for the company.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
long long distinctNames(vector<string>& ideas) {
unordered_map<string, unordered_set<int>> notSwapWith;
for(auto& i : ideas) notSwapWith[i.substr(1)].insert(i[0]);

long long res = 0;
long long dp[26][26] = {};

for(auto& i : ideas) {
string suf = i.substr(1);
auto& us = notSwapWith[suf];
for(char c = 'a'; c <= 'z'; c++) {
if(us.count(c)) continue;
dp[c][i[0] - 'a']++;
}
}

for(auto& i : ideas) {
string suf = i.substr(1);
auto& us = notSwapWith[suf];
for(char c = 'a'; c <= 'z'; c++) {
if(us.count(c)) continue;
res += dp[i[0]][c-'a'];
}
}

return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/06/12/PS/LeetCode/naming-a-company/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.