All problems

Longest Happy Prefix

Hard · string matching

You are given a string s of lowercase letters.

Call a block of letters happy if it is shorter than s, it is not empty, it matches the first letters of s, and it also matches the last letters of s. For example, "abra" is happy for "abracadabra": the string starts with abra and ends with abra.

Return the longest happy block. If there is none, return the empty string.

The start block and the end block may overlap each other. For "aaa" the longest happy block is "aa".

Examples

Example 1

Input: s = "abracadabra"

Output: "abra"

The string starts with "abra" and ends with "abra". No longer block (shorter than the whole string) does both.

Example 2

Input: s = "abcdef"

Output: ""

No first letters equal the last letters of the same length, so there is no happy block.

Example 3

Input: s = "aaa"

Output: "aa"

The first two letters and the last two letters are both "aa". The blocks overlap in the middle letter.

Constraints