Find the longest non-empty prefix of a string that is also a suffix, without using the whole string itself.
Longest Happy Prefix
Given a string s, return the longest proper prefix of s that is also a suffix of s.
A proper prefix is a prefix that is not equal to the entire string. A suffix is a substring that ends at the last character.
If no such prefix exists, return an empty string.
Your task is to find the longest prefix of s that appears again at the end of s.
Input Format
- A single string
s. - The string contains lowercase English letters.
Output Format
- Return the longest proper prefix of
sthat is also a suffix. - If none exists, return
"".
Constraints
sconsists of lowercase English letters.- The answer must be a proper prefix, so it cannot equal
sitself.
Example 1
Input
s = "level"
Output
"l"
Explanation
The prefixes are "l", "le", "lev", "leve". The suffixes are "l", "el", "vel", "evel". The longest string that is both a prefix and a suffix is "l".
Example 2
Input
s = "ababab"
Output
"abab"
Explanation
"abab" is both a prefix and a suffix, and it is the longest such proper prefix.
Show 1 more example
Example 3
Input
s = "leetcodeleet"
Output
"leet"
Explanation
The prefix "leet" also appears as the suffix, and no longer proper prefix matches.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.