Longest Repeated Fragment

Hard

You are given a string text of lowercase English letters. A repeat is a contiguous piece of the string that occurs in it at least twice. The occurrences may overlap. Return the longest repeat. If several repeats share the maximum length, return the one whose second occurrence starts earliest, that is, the one you would see repeat first while reading the string left to right. If no piece repeats, return an empty string.

Example 1

text='abracadabra' → 'abra'

The piece "abra" occurs at the start and at the end, and no piece of length 5 occurs twice.

Example 2

text='aaaa' → 'aaa'

"aaa" starts at position 0 and at position 1: occurrences may overlap.

Example 3

text='xyz' → ''

All letters differ, nothing repeats, so the answer is the empty string.

Constraints

2 ≤ len(text) ≤ 3·10⁴
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Binary Search Suffix Array Sliding Window Hash Function Rolling Hash

Similar problems

Suffixes Echoing the Start Hard Longest Piece Seen Twice Medium Longest Shared Route Segment Hard First Window with a Given Fingerprint Hard Word Near an Anchor Hard

Input

text='abracadabra'

Expected

'abra'

Run checks the first 3 tests in your browser. Submit checks all 119 tests on the server, hidden ones included.