leetcode

commit 904ad8f99cda635f793ab15f6f2465ac2e7ab514
parent d66cc2fc391d504ec4e8d77df4f887ea70d7ac34
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu,  9 Feb 2023 14:25:30 +0100

Daily Problem

Diffstat:
A
Problems/2306.cpp
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 45 insertions(+), 0 deletions(-)
diff --git a/Problems/2306.cpp b/Problems/2306.cpp
@@ -0,0 +1,44 @@
+// Group by first letter, 637ms
+class Solution {
+public:
+  long long distinctNames(vector<string> &ideas) {
+    array<unordered_set<string>, 26> um;
+    for (const auto &idea : ideas)
+      um[idea.front() - 'a'].insert(idea.substr(1));
+
+    long long res = 0ll;
+    for (int i = 0; i < 26; i++) {
+      for (int j = i + 1; j < 26; j++) {
+        long long c1 = 0ll, c2 = 0ll;
+        for (const auto &s : um[i]) c1 += !um[j].count(s);
+        for (const auto &s : um[j]) c2 += !um[i].count(s);
+        res += c1 * c2;
+      }
+    }
+
+    return res * 2;
+  }
+};
+
+// Group by suffix, 373ms
+class Solution {
+public:
+  long long distinctNames(vector<string> &ideas) {
+    unordered_map<string, bitset<32>> um;
+    unordered_map<bitset<32>, int> cnt;
+
+    for (const auto &idea : ideas) um[idea.substr(1)].set(idea.front() - 'a');
+    for (const auto &[k, v] : um) cnt[v]++;
+
+    long long res = 0ll;
+    for (auto it1 = cnt.begin(); it1 != cnt.end(); it1++) {
+      for (auto it2 = next(it1); it2 != cnt.end(); it2++) {
+        int same = (it1->first & it2->first).count();
+        res += (it2->first.count() - same) * (it1->first.count() - same) *
+               it1->second * it2->second;
+      }
+    }
+
+    return res * 2;
+  }
+};
diff --git a/README.md b/README.md
@@ -397,6 +397,7 @@ for solving problems.
 |  2265  |   Medium   | [Count Nodes Equal to Average of Subtree](Problems/2265.cpp)                                     |
 |  2279  |   Medium   | [Maximum Bags With Full Capacity of Rocks](Problems/2279.cpp)                                    |
 |  2285  |   Medium   | [Maximum Total Importance of Roads](Problems/2285.cpp)                                           |
+|  2306  |    Hard    | [Naming a Company](Problems/2306.cpp)                                                            |
 |  2316  |   Medium   | [Count Unreachable Pairs of Nodes in an Undirected Graph](Problems/2316.cpp)                     |
 |  2326  |   Medium   | [Spiral Matrix IV](Problems/2326.cpp)                                                            |
 |  2331  |    Easy    | [Evaluate Boolean Binary Tree](Problems/2331.cpp)                                                |