<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:
    def longestDupSubstring(self, s: str) -> str:
        def search(length: int) -> str:
            """Search for a duplicate substring of a given length using a rolling hash."""
            MOD = 2**63 - 1  # A large prime number for modulo operation
            base = 26  # Base for the rolling hash, since there are 26 lowercase letters
            
            # Compute the hash of the first 'length' characters
            current_hash = 0
            for i in range(length):
                current_hash = (current_hash * base + ord(s[i]) - ord('a')) % MOD
            
            # Store hashes in a set to detect duplicates
            seen = {current_hash}
            baseL = pow(base, length, MOD)  # Precompute base^length % MOD
            
            for start in range(1, len(s) - length + 1):
                # Roll the hash to the next substring
                current_hash = (current_hash * base - (ord(s[start - 1]) - ord('a')) * baseL + ord(s[start + length - 1]) - ord('a')) % MOD
                
                if current_hash in seen:
                    return s[start:start + length]
                seen.add(current_hash)
            
            return ""
        
        # Binary search for the maximum length of the duplicated substring
        left, right = 1, len(s)
        result = ""
        
        while left <= right:
            mid = (left + right) // 2
            dup = search(mid)
            if dup:
                result = dup
                left = mid + 1  # Try to find a longer duplicate
            else:
                right = mid - 1  # Try to find a shorter duplicate
        
        return result

# Example usage:
solution = Solution()
print(solution.longestDupSubstring("banana"))  # Output: "ana"
print(solution.longestDupSubstring("abcd"))    # Output: ""
20900