1044. Longest Duplicate Substring

https://leetcode.com/problems/longest-duplicate-substring/description/

solution

#  Binary search: "banana", the answer must between 0 to 5, we can guess 3 at the first time.
#  We will check every possible substring with length 3 to see if we can find any duplicate.

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        def has_duplicate(length):
            seen = set()
            for i in range(n - length + 1):
                substring = s[i : i + length]
                if substring in seen:
                    return substring
                seen.add(substring)
            return ''

        n = len(s)
        left, right = 0, n
        longest_dup = ''

        while left < right:
            mid = (left + right + 1) // 2
            current_dup = has_duplicate(mid)
            longest_dup = current_dup or longest_dup
            if current_dup:
                left = mid
            else:
                right = mid - 1

        return longest_dup

时间复杂度：O(n^2log(n)) 空间复杂度：O(n^2)