Longest Happy Prefix
Longest proper prefix of `s` that is also a suffix — KMP failure function.
3 min read
strings kmp
Problem#
A “happy prefix” is a non-empty prefix of s that is also a suffix (excluding s itself). Return the longest happy prefix, or "" if none exists.
Examples#
s = "level"→"l".s = "ababab"→"abab".s = "leetcodeleet"→"leet".
Constraints#
1 <= s.length <= 10^5, lowercase letters.
Hints#
Hint
This is exactly the value at the end of the KMP failure (lps) array.
Approach#
Compute the KMP prefix function lps[i] = longest proper prefix of s[0..i] that is also a suffix. The answer is s.substr(0, lps[n-1]).
Solution#
class Solution {public: string longestPrefix(string s) { int n = s.size(); vector<int> lps(n, 0); int k = 0; for (int i = 1; i < n; ++i) { while (k > 0 && s[k] != s[i]) k = lps[k - 1]; if (s[k] == s[i]) ++k; lps[i] = k; } return s.substr(0, lps[n - 1]); }};func longestPrefix(s string) string { n := len(s) lps := make([]int, n) k := 0 for i := 1; i < n; i++ { for k > 0 && s[k] != s[i] { k = lps[k-1] } if s[k] == s[i] { k++ } lps[i] = k } return s[:lps[n-1]]}class Solution: def longestPrefix(self, s: str) -> str: n = len(s) lps = [0] * n k = 0 for i in range(1, n): while k > 0 and s[k] != s[i]: k = lps[k - 1] if s[k] == s[i]: k += 1 lps[i] = k return s[:lps[n - 1]]function longestPrefix(s) { const n = s.length; const lps = new Array(n).fill(0); let k = 0; for (let i = 1; i < n; i++) { while (k > 0 && s[k] !== s[i]) k = lps[k - 1]; if (s[k] === s[i]) k++; lps[i] = k; } return s.slice(0, lps[n - 1]);}class Solution { public String longestPrefix(String s) { int n = s.length(); int[] lps = new int[n]; int k = 0; for (int i = 1; i < n; i++) { while (k > 0 && s.charAt(k) != s.charAt(i)) k = lps[k - 1]; if (s.charAt(k) == s.charAt(i)) k++; lps[i] = k; } return s.substring(0, lps[n - 1]); }}function longestPrefix(s: string): string { const n = s.length; const lps: number[] = new Array(n).fill(0); let k = 0; for (let i = 1; i < n; i++) { while (k > 0 && s[k] !== s[i]) k = lps[k - 1]; if (s[k] === s[i]) k++; lps[i] = k; } return s.slice(0, lps[n - 1]);}Editorial#
KMP’s prefix function is defined precisely as “longest proper prefix that’s also a suffix” for every prefix length, computed in O(N) with a single linear scan. The inner while is the failure jump — falling back through earlier lps values whenever the current character mismatches the next candidate.
Complexity#
- Time: O(N).
- Space: O(N).
Concept revision#
Related#