DSA problem
Longest Happy Prefix
A string is called a happy prefix if it is a non-empty prefix which is also a suffix (excluding the entire string itself). Given a string s, return the longest happy prefix of s. If no such prefix exists, return an empty string.
For example, in the string "level", the prefix "l" is also the last character, so "l" is a happy prefix; longer prefixes do not match the corresponding suffix. In "ababab", the prefix "abab" is also the suffix "abab", so "abab" is the longest happy prefix.
A naïve solution iterates over each possible prefix length k from n - 1 down to 1 and checks whether the first k characters equal the last k characters. Each comparison is O(k) and there are O(n) candidates, giving O(n^2) total time. For long strings (up to 10^5 characters in the constraints) this is too slow.
The optimal solution is the failure function (a.k.a. prefix function) from the KMP string-matching algorithm. For each position i, fail[i] is the length of the longest proper prefix of s[0..i] that is also a suffix of s[0..i]. fail[n - 1] is therefore the answer's length, and the answer itself is s[0 .. fail[n - 1]]. Building the array takes a single O(n) pass with O(n) auxiliary space.
Examples
s = "level""l"s = "ababab""abab"s = "leetcodeleet""leet"Constraints
- 1 <= s.length <= 10^5
- s contains only lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.