Longest Happy Prefix — Solution in Python, Java & C++
Longest Happy Prefix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Longest Happy Prefix is a hard coding problem on strings, rolling hash and KMP Algorithm, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Strings, Rolling Hash, KMP Algorithm
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A happy prefix is a non-empty prefix that is also a suffix, but not the whole string.
Given s, return its longest happy prefix, or the empty string if it has none.
Example 1
Input: s = "level"
Output: l
Explanation: Prefixes that are also suffixes: "l". "le" is not a suffix.
Example 2
Input: s = "ababab"
Output: abab
Explanation: "abab" is both a prefix and a suffix; "ababab" itself does not count.
Example 3
Input: s = "codekairo"
Output:
Explanation: No proper prefix is also a suffix.
Constraints
1 <= s.length <= 100000s consists of lowercase English letters.
Hints for Longest Happy Prefix
Hint 1
This is exactly the value KMP's failure function computes at the last index.
Hint 2
fail[i]is the length of the longest proper prefix ofs[0..i]that is also a suffix of it.Hint 3
Build
failleft to right, falling back throughfail[j-1]on a mismatch.
How to solve Longest Happy Prefix
The longest happy prefix is by definition the last value of KMP's prefix function, so the whole problem is one failure-function build.
Approach
- Set
fail[0] = 0. - For each
ifrom 1, startj = fail[i-1]and, whilej > 0ands[i] != s[j], fall back toj = fail[j-1]. - If
s[i] == s[j], incrementj; storefail[i] = j. - Return the first
fail[n-1]characters ofs.
Why it works
The fallback chain j, fail[j-1], fail[fail[j-1]-1], … enumerates every border of the current prefix in decreasing length, so the first one that can be extended by s[i] gives the longest border of the prefix ending at i. Because fail never counts the whole string, the result is automatically proper.
Complexity
- Time —
O(n) — the fallback chain is amortised constant - Space —
O(n)
Pitfalls
- Comparing every prefix with the matching suffix directly is O(n²) and times out.
- Returning
sitself when the string is uniform — the prefix must be proper, whichfailguarantees. - A rolling hash also works but needs a double hash to be safe against collisions at this input size.
Reference solution
Python
def longestPrefix(s: str) -> str:
n = len(s)
fail = [0] * n
for i in range(1, n):
j = fail[i - 1]
while j > 0 and s[i] != s[j]:
j = fail[j - 1]
if s[i] == s[j]:
j += 1
fail[i] = j
return s[:fail[n - 1]]Java
public static String longestPrefix(String s) {
int n = s.length();
int[] fail = new int[n];
for (int i = 1; i < n; i++) {
int j = fail[i - 1];
while (j > 0 && s.charAt(i) != s.charAt(j)) j = fail[j - 1];
if (s.charAt(i) == s.charAt(j)) j++;
fail[i] = j;
}
return s.substring(0, fail[n - 1]);
}C++
string longestPrefix(string s) {
int n = (int) s.size();
vector<int> fail(n, 0);
for (int i = 1; i < n; i++) {
int j = fail[i - 1];
while (j > 0 && s[i] != s[j]) j = fail[j - 1];
if (s[i] == s[j]) j++;
fail[i] = j;
}
return s.substr(0, fail[n - 1]);
}JavaScript
var longestPrefix = function(s) {
var n = s.length;
var fail = [];
for (var t = 0; t < n; t++) fail.push(0);
for (var i = 1; i < n; i++) {
var j = fail[i - 1];
while (j > 0 && s.charAt(i) !== s.charAt(j)) j = fail[j - 1];
if (s.charAt(i) === s.charAt(j)) j++;
fail[i] = j;
}
return s.substr(0, fail[n - 1]);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings