<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 _td_dp(s):
            # MLE
            @cache
            def _dfs(i, j, l):
                
                if i >= j:
                    return l, l

                if j == n:
                    return l, i

                if s[i] != s[j]:
                    l1, r1 = _dfs(i+1, j, i+1)
                    l2, r2 = _dfs(i, j+1, i)
                    return ((l, i) if (i - l >= r1 - l1 and i - l >= r2 - l2) 
                                else (l1, r1) if r1 - l1 > r2 - l2 
                                else (l2, r2))

                return _dfs(i+1, j+1, l)

            n = len(s)

            l, r = _dfs(0, 1, 0)

            return s[l:r]

        def _bin_search(s):
            def _check(m):
                seen = set()
                for i in range(n - m + 1):
                    if s[i:i+m] in seen:
                        return True
                    seen.add(s[i:i+m])
                return False

            n = len(s)
            l, r = 1, n
            while l <= r:
                m = (l + r) // 2
                if not _check(m):
                    r = m - 1
                else:
                    l = m + 1

            seen = set()
            for i in range(n - r + 1):
                if s[i:i+r] in seen:
                    return s[i:i+r]
                seen.add(s[i:i+r])

            return ""

        return _bin_search(s)
239800