leetcode

commit d490d13063634c4aa9a2dfb12551ec0e5ff2d248
parent f54c6230f9feaa77f3ec7fe545aca527bc0ebd28
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed,  1 Nov 2023 22:46:58 +0000

1 Random Problem

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

2 files changed, 45 insertions(+), 0 deletions(-)
diff --git a/Problems/0318.cpp b/Problems/0318.cpp
@@ -0,0 +1,44 @@
+class Solution {
+  public:
+    int maxProduct(const vector<string> &words) {
+        static uint32_t masks[1001];
+
+        int res = 0;
+        for (int i = 0; i < words.size(); i++) {
+            uint32_t mask = 0;
+            for (const char c : words[i])
+                mask |= 1 << (c & 0x1F);
+            masks[i] = mask;
+            for (int j = 0; j < i; j++) {
+                if ((masks[i] & masks[j]) == 0) {
+                    res = max(res, (int)(words[i].size() * words[j].size()));
+                }
+            }
+        }
+
+        return res;
+    }
+};
+
+class Solution {
+  public:
+    int maxProduct(const vector<string> &words) {
+        unordered_map<int, int> um;
+
+        int res = 0;
+        for (int i = 0; i < words.size(); i++) {
+            uint32_t mask = 0;
+            for (const char c : words[i])
+                mask |= 1 << (c & 0x1F);
+            um[mask] = max(um[mask], (int)words[i].size());
+        }
+
+        for (const auto [k1, v1] : um) {
+            for (const auto [k2, v2] : um) {
+                if ((k1 & k2) == 0) res = max(res, v1 * v2);
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -244,6 +244,7 @@ for solving problems.
 |  0309  |   Medium   | [Best Time to Buy and Sell Stock with Cooldown](Problems/0309.cpp)                                 |
 |  0310  |   Medium   | [Minimum Height Trees](Problems/0310.cpp)                                                          |
 |  0316  |   Medium   | [Remove Duplicate Letters](Problems/0316.cpp)                                                      |
+|  0318  |   Medium   | [Maximum Product of Word Lengths](Problems/0318.cpp)                                               |
 |  0319  |   Medium   | [Bulb Switcher](Problems/0319.cpp)                                                                 |
 |  0322  |   Medium   | [Coin Change](Problems/0322.cpp)                                                                   |
 |  0326  |    Easy    | [Power of Three](Problems/0326.cpp)                                                                |