A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 187. Repeated DNA Sequences, the solution in this repository is mainly a two pointers solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, bit manipulation.
The notes already sitting in the source point us in the right direction:
- TLE
- 31 / 32 test cases passed.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are findRepeatedDnaSequences, getTable, next, KMPSearch, strStr.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//TLE
02//31 / 32 test cases passed.
03class Solution {
04public:
05 vector<string> findRepeatedDnaSequences(string s) {
06 set<string> ans;
07
08 for(int i = 0; i + 10 <= s.size(); i++){
09 string pattern = s.substr(i, 10);
10 size_t found = s.find(pattern, i+1);
11 if(found != string::npos){
12 ans.insert(pattern);
13 }
14 }
15
16 return vector<string>(ans.begin(), ans.end());
17 }
18};
19
20//KMP
21//TLE
22//31 / 32 test cases passed.
23class Solution {
24public:
25 vector<int> getTable(string& pattern){
26 vector<int> next(pattern.size(), -1);
27
28 for(int r = 1, l = -1; r < pattern.size(); r++) {
29 /*
30 if l is -1, we compare from the start of pattern
31 */
32 /*
33 compare pattern[l+1] and pattern[r],
34 if they are different,
35 we go back to compare next[l]+1 with r
36 */
37 while(l != -1 && pattern[l+1] != pattern[r]){
38 l = next[l];
39 }
40
41 // assert( l == -1 || pattern[l+1] == pattern[r]);
42 if( pattern[l+1] == pattern[r]){
43 /*
44 pattern[?:l+1] and patter[?:r] are the same substring,
45 when next time we fail to match pattern[r+1],
46 we will fallback to l+2
47
48 "next" table stores the end position of the last same substring
49 */
50 next[r] = l+1;
51 l++;
52 }
53 }
54
55 return next;
56 };
57
58 int KMPSearch(string& text, string& pattern, vector<int>& next){
59 int tail = -1;
60
61 for(int i = 0; i < text.size(); i++){
62 /*
63 if tail == -1, that means we will match from the start of "pattern"
64 */
65 while(tail != -1 && text[i] != pattern[tail+1]){
66 /*
67 if tail+1 and i don't match, we then fall back to compare former part of "pattern" to current part of "text"
68 */
69 tail = next[tail];
70 }
71
72 if(text[i] == pattern[tail+1]){
73 tail++;
74 }
75 //we can consider tail as the current matched length
76
77 if( tail == pattern.size()-1){
78 return i - tail;
79 }
80 }
81
82 return -1;
83 };
84
85 int strStr(string haystack, string needle) {
86 if(needle == "") return 0;
87 int i = 0, j = 0;
88
89 vector<int> next = getTable(needle);
90
91 // for(int i = 0; i < next.size(); i++){
92 // cout << next[i];
93 // }
94 // cout << endl;
95
96 return KMPSearch(haystack, needle, next);
97 }
98 vector<string> findRepeatedDnaSequences(string s) {
99 vector<string> ans;
100
101 for(int i = 0; i + 10 <= s.size(); i++){
102 string tofind = s.substr(i+1);
103 string pattern = s.substr(i, 10);
104 if(find(ans.begin(), ans.end(), pattern) != ans.end()){
105 continue;
106 }
107 vector<int> next = getTable(pattern);
108 if(KMPSearch(tofind, pattern, next) != -1){
109 ans.push_back(pattern);
110 }
111 }
112
113 return ans;
114 }
115};
116
117//Bit manipulation + Hashmap
118//https://leetcode.com/problems/repeated-dna-sequences/discuss/53867/Clean-Java-solution-(hashmap-%2B-bits-manipulation)
119//Runtime: 140 ms, faster than 32.45% of C++ online submissions for Repeated DNA Sequences.
120//Memory Usage: 15.6 MB, less than 13.54% of C++ online submissions for Repeated DNA Sequences.
121class Solution {
122public:
123 vector<string> findRepeatedDnaSequences(string s) {
124 unordered_set<int> words; //substrings that appear once
125 unordered_set<int> doubleWords; //appear twice
126 unordered_map<char, int> bitRepresentation;
127
128 //we use 2 bit to represent a char
129 bitRepresentation['A'] = 0;
130 bitRepresentation['C'] = 1;
131 bitRepresentation['G'] = 2;
132 bitRepresentation['T'] = 3;
133
134 vector<string> ans;
135
136 // cout << s.size() << " " << (int)s.size() - 10 + 1 << endl;
137
138 /*
139 (int)s.size():
140 Need to convert it from size_t to int!!
141 Because size_t is unsigned, and (size_t)0-10+1 will be 18446744073709551607 which is larger than 0!
142 */
143 for(int i = 0; i < (int)s.size() - 10 + 1; i++){
144 //convert s.substr(i, 10) into its bit representation
145 int value = 0;
146 for(int j = i; j < i+10; j++){
147 value = (value << 2) + bitRepresentation[s[j]];
148 }
149
150 //if the substring appear once but not twice
151 //a.k.a, it's the second time the substring appears
152 if(!words.insert(value).second && doubleWords.insert(value).second){
153 ans.push_back(s.substr(i, 10));
154 }
155 }
156
157 return ans;
158 }
159};
160
161//Bit manipulation + Hashset
162//https://leetcode.com/problems/repeated-dna-sequences/discuss/53877/I-did-it-in-10-lines-of-C%2B%2B
163//Runtime: 84 ms, faster than 73.64% of C++ online submissions for Repeated DNA Sequences.
164//Memory Usage: 15.9 MB, less than 13.54% of C++ online submissions for Repeated DNA Sequences.
165class Solution {
166public:
167 vector<string> findRepeatedDnaSequences(string s) {
168 int n = s.size();
169 vector<string> ans;
170 unordered_set<int> seen, seen_mul;
171
172 int encoded = 0;
173
174 //need to ensure substring of length <= 9 won't be put into the set
175 for(int i = 0; i < 9; ++i){
176 encoded = ((encoded << 2) & 0xFFFFF) | ((s[i]>>1) & 3);
177 }
178
179 for(int i = 9; i < n; ++i){
180 /*
181 note:
182 A: 65 = 1000001, last 3 bit: 1, 3rd+2nd last bits: 0
183 C: 67 = 1000011, last 3 bit: 3, 3rd+2nd last bits: 1
184 G: 71 = 1000111, last 3 bit: 7, 3rd+2nd last bits: 3
185 T: 84 = 1010100, last 3 bit: 4, 3rd+2nd last bits: 2
186 their 3rd+2nd last bits are all different,
187 so we can encode a string of "ACGT" by their last 3rd+2nd last bits
188
189 to take 3rd+2nd last bits,
190 we use s[i]>>1 & 3(this take 2 bits for each char),
191 not s[i] & 6!!(it will take 3 bits)
192 */
193
194 /*
195 the original version use the last 3 digits to represent each char,
196 so it needs totally 30 char for each substr,
197 it's fine to use "int" to contain it,
198 but there will be (encoded << 3) later and it will cause overflow
199 */
200 // cout << s[i] << ": " << ((s[i]>>1) & 3) << endl;
201 encoded = ((encoded << 2) & 0xFFFFF) | ((s[i]>>1) & 3);
202 // encoded = ((encoded << 2) & 0xFFFFF) | (s[i] - 64) % 5;
203 // if(i >= 9) cout << s.substr(i-9, 10) << ", " << encoded << endl;
204 if(seen_mul.find(encoded) == seen_mul.end() &&
205 !seen.insert(encoded).second){
206 ans.push_back(s.substr(i-9, 10));
207 seen_mul.insert(encoded);
208 }
209 }
210
211 return ans;
212 }
213};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.