Start That Matches the End

Hard

You are given a string word. Find the longest non-empty piece that the string both starts with and ends with. The whole string itself does not count, but the starting and ending copies may overlap. Return that piece, or an empty string if there is none.

Example 1

word='abcab' → 'ab'

The word starts and ends with "ab". The longer starts "abc" and "abca" are not endings of the word.

Example 2

word='aaab' → ''

The last letter "b" never appears at the start, so no such piece exists.

Example 3

word='abababa' → 'ababa'

"ababa" is both the start and the end; the two copies overlap, which is allowed.

Constraints

1 ≤ len(word) ≤ 10⁵
word consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String String Matching Hash Function Rolling Hash

Similar problems

Palindrome by Adding Letters in Front Hard Suffixes Echoing the Start Hard Peel Off a Repeated Start Hard Word Near an Anchor Hard Chop and Append Hard

Input

word='abcab'

Expected

'ab'

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