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 "".)
Example 1:
Input: "banana" Output: "ana"
Example 2:
Input: "abcd" Output: ""
Note:
<li><code>2 <= S.length <= 10^5</code></li>
<li><code>S</code> consists of lowercase English letters.</li>