leetcode

commit 0a8792642f8a977eadfc9fc66266f46c430ea6a7
parent 4520be275682245aaf9c1e1e761bfd9f631171e8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  9 Jul 2023 09:05:08 +0200

Daily Problem

Diffstat:
A
Problems/2272.cpp
 | 
24
++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 25 insertions(+), 0 deletions(-)
diff --git a/Problems/2272.cpp b/Problems/2272.cpp
@@ -0,0 +1,24 @@
+class Solution {
+public:
+  int largestVariance(const string &s) {
+    int count[27] = {0}, res = 0;
+    for (char c : s) count[c & 0xF]++;
+
+    for (char ma = 'a'; ma <= 'z'; ma++) {
+      for (char mi = 'a'; mi <= 'z'; mi++) {
+        if (ma == mi || !count[ma & 0xF] || !count[mi & 0xF]) continue;
+        int mac = 0, mic = 0, rst = count[mi & 0xF];
+        for (char c : s) {
+          if (c == ma)
+            mac++;
+          else if (c == mi)
+            mic++, rst--;
+
+          if (mic > 0) res = max(res, mac - mic);
+          if (mac < mic && rst > 0) mac = mic = 0;
+        }
+      }
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -553,6 +553,7 @@ for solving problems.
 |  2244  |   Medium   | [Minimum Rounds to Complete All Tasks](Problems/2244.cpp)                                        |
 |  2246  |    Hard    | [Longest Path With Different Adjacent Characters](Problems/2246.cpp)                             |
 |  2265  |   Medium   | [Count Nodes Equal to Average of Subtree](Problems/2265.cpp)                                     |
+|  2272  |    Hard    | [Substring With Largest Variance](Problems/2272.cpp)                                             |
 |  2279  |   Medium   | [Maximum Bags With Full Capacity of Rocks](Problems/2279.cpp)                                    |
 |  2285  |   Medium   | [Maximum Total Importance of Roads](Problems/2285.cpp)                                           |
 |  2300  |   Medium   | [Successful Pairs of Spells and Potions](Problems/2300.cpp)                                      |