<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>

"""
Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.
Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is "".

"ababab" -> "abab"
"abcdef" -> ""

Can iterate through every possible substring, keep track of what's been seen before. If seen and came across again, return.
Iterate smartly by doing largest length first, then iterate over first indices. This also means only need memory for current length.

"""

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        n = len(s)
        def checkDiff(diff: int) -> str:
            seen_substrings = set()
            for start in range(n-diff):
                end = start+diff
                substring = s[start:end+1]
                if substring in seen_substrings:
                    return substring
                seen_substrings.add(substring)
            return ""
        
        l, r = 0, n-1
        best = ""
        while l <= r:
            m = l + (r-l)//2
            substring = checkDiff(m)
            if substring != "":
                l = m+1
                best = substring
            else:
                r = m-1
        return best
238800