leetcode

commit 5c32b2fa0cd72bc58ac2cd561385f566a835f328
parent 521604886899958097481856e698ff88848abcbf
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 10 Feb 2023 14:59:54 +0100

Data Structure II: Day 7

Diffstat:
A
Problems/0763.cpp
 | 
29
+++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 30 insertions(+), 0 deletions(-)
diff --git a/Problems/0763.cpp b/Problems/0763.cpp
@@ -0,0 +1,29 @@
+class Solution {
+public:
+  vector<int> partitionLabels(string s) {
+    unordered_set<char> seen;
+    array<int, 26> count = {0};
+    vector<int> res;
+
+    for (char c : s) count[c - 'a']++;
+
+    int len = 0, needed = 0;
+    for (int i = 0; i < s.size(); i++) {
+      len++;
+      if (seen.count(s[i]))
+        needed--;
+      else {
+        needed += count[s[i] - 'a'] - 1;
+        seen.insert(s[i]);
+      }
+
+      if (!needed) {
+        res.push_back(len);
+        seen.clear();
+        len = 0;
+      }
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -270,6 +270,7 @@ for solving problems.
 |  0746  |    Easy    | [Min Cost Climbing Stairs](Problems/0746.cpp)                                                    |
 |  0747  |    Easy    | [Largest Number At Least Twice of Others](Problems/0747.cpp)                                     |
 |  0752  |   Medium   | [Open the Lock](Problems/0752.cpp)                                                               |
+|  0763  |   Medium   | [Partition Labels](Problems/0763.cpp)                                                            |
 |  0783  |    Easy    | [Minimum Distance Between BST Nodes](Problems/0783.cpp)                                          |
 |  0784  |   Medium   | [Letter Case Permutation](Problems/0784.cpp)                                                     |
 |  0785  |   Medium   | [Is Graph Bipartite?](Problems/0785.cpp)                                                         |