leetcode 1044. Longest Duplicate Substring

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

Still work in progress.
current verion fails due to time limit.

class Solution:
    # 2506ms
    def longestDupSubstring(self, s: str) -> str:
        def find_duplicated(s, k):
            for i in range(len(s) - k + 1):
                substr = s[i:i+k]
                if s.find(substr, i+1) != -1:
                    return substr
            return ''
        
        # binary search of length of the answer
        lower = 0
        upper = len(s)
        ans = ''
        
        while lower < upper:
            print (lower, upper)
            middle = (lower + upper) // 2
            dup = find_duplicated(s, middle)
            # if not found, lower the `upper` to `middle`
            # Otherwise, raise the `lower` to `middle` + 1
            if dup == "":
                upper = middle
            else:
                
                lower = middle + 1
                ans = dup

        return ans