Find longest duplicated substring

You are given a string `s` consisting of lowercase English letters. A **substring** of `s` is any contiguous sequence of characters, i.e., `s[i..j)` for `0 ≤ i < j ≤ len(s)`. Design an algorithm to find **any one** of the longest substrings that appears **at least twice** in `s`. The two occurrences may overlap. If no substring appears at least twice, return the empty string. ### Requirements - Input: a string `s` of length `n` (e.g., `1 ≤ n ≤ 2 × 10^5`). - Output: a string representing one of the longest duplicated substrings. - Aim for an algorithm substantially better than the naive `O(n^2)` substring comparison approach. ### Examples - `s = "banana"` - Possible duplicated substrings: "a", "an", "ana" - Longest length is 3 ("ana"), so acceptable outputs include `"ana"`. - `s = "abcd"` - No duplicated substring, so output should be `""` (empty string). Describe your algorithm, its time and space complexity, and how it scales for large `n`.