<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(object):
    def rolling_hash(self, s, window):
        multiplier = 31
        mod = 1000000007

        hashed_value = 0
        for i in range(window):
            hashed_value = (hashed_value * multiplier + (ord(s[i]) - ord('a') + 1)) % mod

        power = 1
        for i in range(1, window):
            power = (power * multiplier) % mod

        mp = {}
        hashed_value %= mod
        mp[hashed_value] = [0]

        for i in range(1, len(s) - window + 1):
            hashed_value -= ((ord(s[i - 1]) - ord('a') + 1) * power)
            while hashed_value < 0:
                hashed_value += mod
            hashed_value %= mod

            hashed_value *= 31
            hashed_value %= mod
            hashed_value += (ord(s[i + window - 1]) - ord('a') + 1)
            hashed_value %= mod

            if hashed_value in mp:
                for st in mp[hashed_value]:
                    old = s[st: st + window]
                    new_str = s[i: i + window]
                    if old == new_str:
                        return new_str
            mp[hashed_value] = mp.get(hashed_value, []) + [i]

        return ""

    def longestDupSubstring(self, s):
        s_len = len(s)
        start = 1
        end = s_len - 1
        ans = ""

        while start <= end:
            mid = start + (end - start) // 2
            temp = self.rolling_hash(s, mid)
            if temp:
                ans = temp
                start = mid + 1
            else:
                end = mid - 1

        return ans
23300