# ---
# title: 1044. Longest Duplicate Substring
# id: problem1044
# author: Tian Jun
# date: 2020-10-31
# difficulty: Hard
# categories: Hash Table, Binary Search, Suffix Array
# link: <https://leetcode.com/problems/longest-duplicate-substring/description/>
# hidden: true
# ---
# 
# 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: s = "banana"
#     Output: "ana"
#     
# 
# **Example 2:**
# 
#     
#     
#     Input: s = "abcd"
#     Output: ""
#     
# 
# 
# 
# **Constraints:**
# 
#   * `2 <= s.length <= 3 * 104`
#   * `s` consists of lowercase English letters.
# 
# 
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end
