leetcode

commit aab0ccefae5496d4cff8c99b0f9844bc6e1fb35a
parent 080fd5e402784bf5a9671c93e60439957a2b6d6c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 12 Feb 2023 12:55:43 +0100

Data Structure II: Day 9

Diffstat:
A
Problems/0187.cpp
 | 
58
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 59 insertions(+), 0 deletions(-)
diff --git a/Problems/0187.cpp b/Problems/0187.cpp
@@ -0,0 +1,58 @@
+// Left to right
+class Solution {
+public:
+  vector<string> findRepeatedDnaSequences(string s) {
+    if (s.size() <= 10) return {};
+
+    unordered_map<string, int> um;
+    vector<string> res;
+    string sec = "";
+
+    for (int i = 0; i < 10; i++) sec += s[i];
+    um[sec]++;
+    for (int i = 10; i < s.size(); i++) {
+      sec = sec.substr(1) + s[i];
+      if (um[sec]++ == 1) res.push_back(sec);
+    }
+
+    return res;
+  }
+};
+
+// Right to left
+class Solution {
+public:
+  vector<string> findRepeatedDnaSequences(string s) {
+    if (s.size() <= 10) return {};
+
+    unordered_map<string, int> um;
+    vector<string> res;
+    string sec = "";
+
+    for (int i = s.size() - 1; i >= s.size() - 10; i--) sec = s[i] + sec;
+    um[sec]++;
+    for (int i = s.size() - 10 - 1; i >= 0; i--) {
+      sec.pop_back();
+      sec = s[i] + sec;
+      if (um[sec]++ == 1) res.push_back(sec);
+    }
+
+    return res;
+  }
+};
+
+// Bit hacking
+class Solution {
+public:
+  vector<string> findRepeatedDnaSequences(string s) {
+    unordered_map<unsigned, int> um;
+    vector<string> res;
+
+    for (unsigned i = 0, sec = 0; i < s.size(); i++) {
+      sec = sec << 3 & 0x3FFFFFFF | s[i] & 7;
+      if (um[sec]++ == 1) res.push_back(s.substr(i - 9, 10));
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -132,6 +132,7 @@ for solving problems.
 |  0167  |   Medium   | [Two Sum II - Input Array Is Sorted](Problems/0167.cpp)                                          |
 |  0169  |    Easy    | [Majority Element](Problems/0169.cpp)                                                            |
 |  0173  |   Medium   | [Binary Search Tree Iterator](Problems/0173.cpp)                                                 |
+|  0187  |   Medium   | [Repeated DNA Sequences](Problems/0187.cpp)                                                      |
 |  0189  |   Medium   | [Rotate Array](Problems/0189.cpp)                                                                |
 |  0190  |    Easy    | [Reverse Bits](Problems/0190.cpp)                                                                |
 |  0191  |    Easy    | [Number of 1 Bits](Problems/0191.cpp)                                                            |