Problem Description

You are given a string s. Consider all repeated substrings of s: that is, (contiguous) substrings of s that occur 2 or more times in s. These occurrences may overlap.

Return any one repeated substring with the maximum possible length. If s does not contain any repeated substring, return "".

Examples

Example 1:
Input: s = "banana"
Output: "ana"

Example 2:
Input: s = "abcd"
Output: ""

Constraints

• 2 <= s.length <= 3 * 10⁴
• s consists of lowercase English letters.