Longest Happy Prefix

A happy prefix is a non-empty prefix of s (shorter than s) that is also a suffix. Return the longest happy prefix, or "" if there is none.

For "level" the answer is "l"; for "ababab" it is "abab".

The starter code compares every possible length from scratch. It is correct but too slow for long strings.

Examples

Example 1

Input:

longest_happy_prefix('level')

Output:

'l'

Example 2

Input:

longest_happy_prefix('ababab')

Output:

'abab'

Constraints

• 0 <= len(s) <= 200000
• Lower-case letters.