leetcode

commit df2f9c8ec72391b628379c84ea474a1a5168848a
parent d5a8b6d70876bf6a425db8703344d97dafbd7b5e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed,  1 Feb 2023 17:48:29 +0100

LeetCode 75 I: Day 12

Diffstat:
A
Problems/0424.cpp
 | 
18
++++++++++++++++++
A
Problems/0438.cpp
 | 
31
+++++++++++++++++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 51 insertions(+), 0 deletions(-)
diff --git a/Problems/0424.cpp b/Problems/0424.cpp
@@ -0,0 +1,18 @@
+class Solution {
+public:
+  int characterReplacement(string s, int k) {
+    vector<int> counts(26, 0);
+    int n = s.length(), start = 0, maxi = 0, result = 0;
+    for_each(s.begin(), s.end(), [](char &c) { c -= 'A'; });
+
+    for (int end = 0; end < n; end++) {
+      maxi = max(maxi, ++counts[s[end]]);
+      while (end - start - maxi + 1 > k) {
+        counts[s[start++]]--;
+        for (int i = 0; i < 26; i++) maxi = max(maxi, counts[i]);
+      }
+      result = max(result, end - start + 1);
+    }
+    return result;
+  }
+};
diff --git a/Problems/0438.cpp b/Problems/0438.cpp
@@ -0,0 +1,31 @@
+class Solution {
+  typedef unordered_map<char, int> umci;
+  bool um_eq(const umci &goal, const umci &crnt) {
+    for (auto [k, v] : goal) {
+      const auto it = crnt.find(k);
+      if (it == crnt.end()) return false;
+      if ((*it).second != v) return false;
+    }
+    return true;
+  }
+
+public:
+  vector<int> findAnagrams(string s, string p) {
+    if (p.size() > s.size()) return {};
+    unordered_map<char, int> goal, crnt;
+
+    for (int i = 0; i < p.size(); i++) {
+      goal[p[i]]++;
+      crnt[s[i]]++;
+    }
+
+    vector<int> res;
+    for (int i = p.size(); i < s.size(); i++) {
+      if (um_eq(goal, crnt)) res.push_back(i - p.size());
+      crnt[s[i - p.size()]]--;
+      crnt[s[i]]++;
+    }
+    if (um_eq(goal, crnt)) res.push_back(s.size() - p.size());
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -174,10 +174,12 @@ for solving problems.
 |  0413  |   Medium   | [Arithmetic Slices](Problems/0413.cpp)                                                           |
 |  0414  |    Easy    | [Third Maximum Number](Problems/0414.cpp)                                                        |
 |  0415  |    Easy    | [Add Strings](Problems/0415.cpp)                                                                 |
+|  0424  |   Medium   | [Longest Repeating Character Replacement](Problems/0424.cpp)                                     |
 |  0429  |   Medium   | [N-ary Tree Level Order Traversal](Problems/0429.cpp)                                            |
 |  0430  |   Medium   | [Flatten a Multilevel Doubly Linked list](Problems/0430.cpp)                                     |
 |  0433  |   Medium   | [Minimum Genetic Mutation](Problems/0433.cpp)                                                    |
 |  0435  |   Medium   | [Non-overlapping Intervals](Problems/0435.cpp)                                                   |
+|  0438  |   Medium   | [Find All Anagrams in a String](Problems/0438.cpp)                                               |
 |  0445  |   Medium   | [Add Two Numbers II](Problems/0445.cpp)                                                          |
 |  0448  |    Easy    | [Find All Numbers Disappeared in an Array](Problems/0448.cpp)                                    |
 |  0450  |   Medium   | [Delete Node in a BST](Problems/0450.cpp)                                                        |