This problem looks busy at first, but the accepted solution is built around one steady invariant. For 1044. Longest Duplicate Substring, the solution in this repository is mainly a binary search solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. 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: binary search, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- rolling hash + binary search
- WA(something to do with overflow?)
- 14 / 16 test cases passed.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are modPower, gcd, modInverse, modMultiply, longestDupSubstring.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- 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:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
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//rolling hash + binary search
02//WA(something to do with overflow?)
03//14 / 16 test cases passed.
04class Solution {
05public:
06 int modPower(int x, unsigned int y, unsigned int m){
07 if (y == 0)
08 return 1;
09 long long p = modPower(x, y/2, m) % m;
10 p = (p * p) % m;
11
12 return (y%2 == 0)? p : (x * p) % m;
13 };
14
15 // Function to return gcd of a and b
16 int gcd(int a, int b){
17 if (a == 0)
18 return b;
19 return gcd(b%a, a);
20 };
21
22 // Function to find modular inverse of a under modulo m
23 // Assumption: m is prime
24 int modInverse(int a, int m){
25 int g = gcd(a, m);
26 if (g != 1){
27 return -1;
28 }else{
29 // If a and m are relatively prime, then modulo inverse
30 // is a^(m-2) mode m
31 return modPower(a, m-2, m);
32 }
33 };
34
35 int modMultiply(int a, int b, int mod) {
36 int res = 0; // Initialize result
37
38 // Update a if it is more than
39 // or equal to mod
40 a %= mod;
41
42 while (b){
43 /*
44 If b is even then
45 a * b = 2 * a * (b / 2),
46 otherwise
47 a * b = a + a * (b - 1)
48 */
49 // If b is odd, add 'a' to result
50 if(b & 1){
51 res = (res + a) % mod;
52 }
53
54 // Here we assume that doing 2*a
55 // doesn't cause overflow
56 a = (2 * a) % mod;
57
58 b >>= 1; // b = b / 2
59 }
60
61 return res;
62 };
63
64 string longestDupSubstring(string S) {
65 int n = S.size();
66 int p = 26;
67 // int MOD = 1e9 + 7; //slower
68 int MOD = 19260817;
69 int pInv = modInverse(p, MOD);
70
71 //binary search to find right boundary
72 int left = 0, right = n-1;
73 int len;
74
75 string ans;
76
77 vector<int> powers(n);
78 powers[0] = 1;
79 for(int i = 1; i < n; ++i){
80 powers[i] = modMultiply(powers[i-1], p, MOD);
81 }
82
83 while(left <= right){
84 //mid
85 len = left + (right-left)/2;
86 if(len == 0) break;
87 // cout << left << ", " << len << ", " << right << endl;
88
89 //hash value -> start indices
90 unordered_map<long long, vector<int>> hashs;
91
92 long long hash = 0, power = 1;
93
94 for(int i = 0; i < len; ++i){
95 // hash += (S[i]-'a')* power;
96 // power = (power * p) % MOD;
97 hash = (hash + modMultiply(S[i]-'a', powers[i], MOD)) % MOD;
98 }
99 //p^(n-1)
100 // power = (power * pInv) % MOD;
101
102 hashs[hash].push_back(0);
103
104 bool valid = false;
105 for(int start = 1; start+len-1 < n; ++start){
106 hash = (hash - (S[start-1]-'a')) % MOD;
107 hash = modMultiply(hash, pInv, MOD);
108 hash = (hash + modMultiply(S[start+len-1]-'a', powers[len-1], MOD) % MOD);
109
110 if(hashs.find(hash) != hashs.end()){
111 for(int& matched_start : hashs[hash]){
112 if(strcmp((S.substr(matched_start, len)).data(), S.substr(start, len).data()) == 0){
113 //slower
114 // if(S.substr(matched_start, len) == S.substr(start, len)){
115 valid = true;
116 if(len > ans.size())
117 ans = S.substr(start, len);
118 break;
119 }
120 }
121 }
122 if(valid) break;
123 hashs[hash].push_back(start);
124 // for(auto it = hashs.begin(); it != hashs.end(); ++it){
125 // cout << it->first << " ";
126 // }
127 // cout << endl;
128 }
129
130 if(valid){
131 left = len+1;
132 }else{
133 right = len-1;
134 }
135 }
136
137 if(right < 0) return "";
138
139 return ans;
140 }
141};
142
143//different formula of rolling hash, S[0] has largest multiplier
144//https://leetcode.com/problems/longest-duplicate-substring/discuss/291048/C%2B%2B-solution-using-Rabin-Karp-and-binary-search-with-detailed-explaination
145//Runtime: 3132 ms, faster than 6.80% of C++ online submissions for Longest Duplicate Substring.
146//Memory Usage: 442.3 MB, less than 10.46% of C++ online submissions for Longest Duplicate Substring.
147class Solution {
148public:
149 int modPower(int x, unsigned int y, unsigned int m){
150 if (y == 0)
151 return 1;
152 long long p = modPower(x, y/2, m) % m;
153 p = (p * p) % m;
154
155 return (y%2 == 0)? p : (x * p) % m;
156 };
157
158 // Function to return gcd of a and b
159 int gcd(int a, int b){
160 if (a == 0)
161 return b;
162 return gcd(b%a, a);
163 };
164
165 // Function to find modular inverse of a under modulo m
166 // Assumption: m is prime
167 int modInverse(int a, int m){
168 int g = gcd(a, m);
169 if (g != 1){
170 return -1;
171 }else{
172 // If a and m are relatively prime, then modulo inverse
173 // is a^(m-2) mode m
174 return modPower(a, m-2, m);
175 }
176 };
177
178 int modMultiply(int a, int b, int mod) {
179 int res = 0; // Initialize result
180
181 // Update a if it is more than
182 // or equal to mod
183 a %= mod;
184
185 while (b){
186 /*
187 If b is even then
188 a * b = 2 * a * (b / 2),
189 otherwise
190 a * b = a + a * (b - 1)
191 */
192 // If b is odd, add 'a' to result
193 if(b & 1){
194 res = (res + a) % mod;
195 }
196
197 // Here we assume that doing 2*a
198 // doesn't cause overflow
199 a = (2 * a) % mod;
200
201 b >>= 1; // b = b / 2
202 }
203
204 return res;
205 };
206
207 string longestDupSubstring(string S) {
208 int n = S.size();
209 int p = 26;
210 //some large primes: 1e9+7, 19260817, 99999989
211 // int MOD = 1e9 + 7; //slower
212 int MOD = 19260817;
213 int pInv = modInverse(p, MOD);
214
215 //binary search to find right boundary
216 int left = 0, right = n-1;
217 int len;
218
219 string ans;
220
221 vector<int> powers(n);
222 powers[0] = 1;
223 for(int i = 1; i < n; ++i){
224 powers[i] = modMultiply(powers[i-1], p, MOD);
225 }
226
227 while(left <= right){
228 //mid
229 len = left + (right-left)/2;
230 if(len == 0) break;
231 // cout << left << ", " << len << ", " << right << endl;
232
233 //hash value -> start indices
234 unordered_map<long long, vector<int>> hashs;
235
236 long long hash = 0, power = 1;
237
238 for(int i = 0; i < len; ++i){
239 hash = (modMultiply(hash, p, MOD) + (S[i]-'a')) % MOD;
240 }
241
242 hashs[hash].push_back(0);
243
244 bool valid = false;
245 for(int start = 1; start+len-1 < n; ++start){
246 hash = (hash - modMultiply(S[start-1]-'a', powers[len-1], MOD) + MOD) % MOD;
247 hash = (modMultiply(hash, p, MOD) + (S[start+len-1]-'a')) % MOD;
248
249 if(hashs.find(hash) != hashs.end()){
250 for(int& matched_start : hashs[hash]){
251 if(strcmp((S.substr(matched_start, len)).data(), S.substr(start, len).data()) == 0){
252 valid = true;
253 if(len > ans.size())
254 ans = S.substr(start, len);
255 break;
256 }
257 }
258 }
259 if(valid) break;
260 hashs[hash].push_back(start);
261 // for(auto it = hashs.begin(); it != hashs.end(); ++it){
262 // cout << it->first << " ";
263 // }
264 // cout << endl;
265 }
266
267 if(valid){
268 left = len+1;
269 }else{
270 right = len-1;
271 }
272 }
273
274 if(right < 0) return "";
275
276 return ans;
277 }
278};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.