<p>Given a string <code>s</code>, consider all <em>duplicated substrings</em>: (contiguous) substrings of s that occur 2 or more times.&nbsp;The occurrences&nbsp;may overlap.</p>

<p>Return <strong>any</strong> duplicated&nbsp;substring that has the longest possible length.&nbsp;If <code>s</code> does not have a duplicated substring, the answer is <code>&quot;&quot;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "banana"
<strong>Output:</strong> "ana"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "abcd"
<strong>Output:</strong> ""
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= s.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution {

	bool findDup(const string& s, int p, int len, const vector<int>& pos, int pi,
		const vector<int>& hashes) {
		if (p + len > s.size()) {
			return false;
		}
		const int has = hashes[p + len - 1] - hashes[p];
		while ((pi < pos.size()) && (pos[pi] + len <= s.size())) {
			const int h = hashes[pos[pi] + len - 1] - hashes[pos[pi]];
			if (h == has && (s[p + len - 1] == s[pos[pi] + len - 1])) {
				if (s.substr(p, len) == s.substr(pos[pi], len)) {
					return true;
				}
			}
			pi++;
		}
		return false;
	}

public:
	string longestDupSubstring(string s) {
		auto mm = std::minmax_element(s.begin(), s.end());
		if (*mm.first == *mm.second) {
			return s.substr(1);
		}
		unordered_map<char, vector<int>> charMap;
		vector<int> hashes;
		int sum = 0;
		bool dop = false;
		for (int i = 0; i < s.size(); i++) {
			charMap[s[i]].push_back(i);
			sum += s[i];
			hashes.push_back(sum);
		}
		int mbeg = -1;
		int mlen = 0;
		for (auto& entry : charMap) {
			for (int p = 0; p + 1 < entry.second.size(); p++) {
				if (entry.second[p] + mlen >= s.size()) {
					break;
				}
				int len = std::max(mlen, 1);
				const int mhigh = s.size() - entry.second[p];
				int high = len;
				bool found = findDup(s, entry.second[p], len, entry.second, p + 1, hashes);
				bool startFound = found;
				while (found) {
					len = high;
					high = std::min(2 * len, mhigh);
					found = findDup(s, entry.second[p], high, entry.second, p + 1, hashes);
				}
				if (startFound) {
					int diff = high - len;
					while (diff > 1) {
						if (findDup(s, entry.second[p], len + diff / 2, entry.second, p + 1, hashes)) {
							len += diff / 2;
						}
						else {
							high = len + diff / 2;
						}
						diff = high - len;
					}
					if (len > mlen) {
						mlen = len;
						mbeg = entry.second[p];
					}
				}
			}
		}
		if (mbeg >= 0) {
			return s.substr(mbeg, mlen);
		}
		return "";
	}
};
354020