#1392
Longest Happy Prefix
Hard LPS array
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A "happy prefix" is a non-empty prefix that is also a suffix, but not the whole string. Return the longest one, or "".
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest prefix that is also a suffix (not the whole string).
Why this works: that is exactly the last value of the LPS array.
Example: "level"
lps = [0, 0, 0, 0, 1] → "l"✦Hints open one at a time
This is exactly what the KMP failure function computes.
The answer's length is lps[n − 1].
↗Approach
Build the LPS array of s and return the prefix of length lps[n − 1].
</>Solution (Java)
class Solution {
public String longestPrefix(String s) {
int n = s.length();
int[] lps = new int[n];
for (int i = 1, len = 0; i < n; ) {
if (s.charAt(i) == s.charAt(len)) lps[i++] = ++len;
else if (len > 0) len = lps[len - 1];
else lps[i++] = 0;
}
return s.substring(0, lps[n - 1]);
}
}!Common mistake
Comparing every prefix with every suffix — O(n²) and too slow for n = 10^5.
Complexity
- Time: O(n).
- Space: O(n).
Topic: String Pattern Matching
🎬 Episodes 18–19: video coming soon