<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 {
public:
    string_view DupSubstringOfSize(const string_view s, int l) {
        const int size = s.size();
        using T = uint32_t;
        unordered_multimap<T, T> mm(size);
        int64_t hash = 0;
        constexpr int64_t p = 26;
        constexpr int64_t MOD = numeric_limits<T>::max();
        int64_t maxp = 1;
        // From 1 because maxp = p^(l-1)
        for (int i = 1; i < l; ++i) {
            maxp *= p;
            maxp %= MOD;
        }
        for (int i = 0; i < l; ++i) {
            hash *= p;
            hash += s[i] - 'a';
            hash %= MOD;
        }
        if (hash < 0)
            hash += MOD;

        mm.insert({hash, 0});

        int collisions = 0;
        int maxcollisions = 0;
        const int maxpos = size - l;
        for (int i = 0; i < maxpos; ++i) {
            hash -= (s[i] - 'a') * maxp;
            hash *= p;
            hash += s[i + l] - 'a';
            hash %= MOD;
            if (hash < 0)
                hash += MOD;

            auto [it, end] = mm.equal_range(hash);
            int c = 0;
            while (it != end) {
                ++collisions;
                ++c;
                if (s.substr(it->second, l) == s.substr(i + 1, l)) {
                    if (false and collisions > 1) {
                        cout << size - l << " steps, " << collisions
                             << " collisions, " << max(maxcollisions, c)
                             << " maxcollisions." << endl;
                    }
                    return s.substr(it->second, l);
                }

                ++it;
            }
            maxcollisions = max(maxcollisions, c);
            mm.insert({hash, i + 1});
        }
        if (false and collisions) {
            cout << size - l << " steps, " << collisions << " collisions, "
                 << maxcollisions << " maxcollisions." << endl;
        }
        return {};
    }
    bool hasDuplicates(const string_view s) {
        array<uint8_t, 26> chars = {0};
        const int size = s.size();
        for (int i = 0; i < size; ++i) {
            const unsigned n = s[i] - 'a';
            if (chars[n])
                return true;

            chars[n] = 1;
        }
        return false;
    }
    string longestDupSubstring(string s) {
        if (s.size() <= 26 and !hasDuplicates(s)) {
            return {};
        }
        int minlen = 1;
        int maxlen = s.size() - 1;
        string_view found = DupSubstringOfSize(s, maxlen);
        if (!found.empty())
            return string(found);

        string_view last_found = DupSubstringOfSize(s, minlen);
        while (maxlen - minlen > 1) {
            int mid = (maxlen + minlen) / 2;
            found = DupSubstringOfSize(s, mid);
            if (found.empty()) {
                maxlen = mid;
            } else {
                last_found = found;
                minlen = mid;
            }
        }
        return string(last_found);
    }
};
117860