longest-duplicate-substring

Longest Duplicate Substring

LeetCode #: 1044

Difficulty: Hard

Topics: Hash Table, Binary Search.

Problem

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:

• 2 <= S.length <= 10^5
• S consists of lowercase English letters.

Solution Explanation

Reference: [Python] Binary Search by lee215