Longest Happy Prefix

Difficulty: Hard · Topic: Strings & pattern matching

A happy prefix is a non-empty prefix that is also a suffix (but not the whole string). Return the longest happy prefix of s (or "" if none). This is exactly the last value of the KMP failure function.

Examples

longest_happy_prefix("level")
→ "l"

'l' is a prefix and a suffix.

longest_happy_prefix("ababab")
→ "abab"

longest_happy_prefix("abcdef")
→ ""

Target complexity: time O(n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.