Watch 9 video solutions for Longest Happy Prefix, a hard level problem involving String, Rolling Hash, String Matching. This walkthrough by Aditya Verma has 6,383 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).
Given a string s, return the longest happy prefix of s. Return an empty string "" if no such prefix exists.
Example 1:
Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".
Example 2:
Input: s = "ababab" Output: "abab" Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.
Constraints:
1 <= s.length <= 105s contains only lowercase English letters.Problem Overview: Given a string s, return the longest prefix that is also a suffix of the same string, excluding the entire string itself. The prefix and suffix must be identical in characters and order. If none exists, return an empty string.
Approach 1: Brute Force Prefix Check (O(n²) time, O(1) space)
Start from the longest possible prefix length n-1 and move backward. For each length k, compare s[0:k] with the suffix s[n-k:n]. The first match you find is the longest happy prefix. This approach relies on repeated substring comparisons, which makes it quadratic in the worst case when many prefixes partially match. It works for small strings but quickly becomes slow when n grows.
Approach 2: KMP Prefix Function (O(n) time, O(n) space)
This is the most common solution using the prefix function from the string matching family of algorithms. Build the LPS (longest prefix suffix) array used in the Knuth–Morris–Pratt algorithm. While iterating through the string, the array stores the length of the longest prefix that also matches a suffix ending at that index. After processing the full string, lps[n-1] directly gives the length of the longest happy prefix. The key insight is that KMP reuses previous prefix information instead of rechecking characters, which guarantees linear time.
Approach 3: Rolling Hash (O(n) time, O(1) space)
A hashing-based approach compares prefix and suffix hashes as you scan the string from both directions. Maintain a forward rolling hash for the prefix and a backward hash for the suffix. When the two hash values match, record the current length as a candidate answer. With a good base and modulus, hash collisions are extremely rare. This method relies on techniques from rolling hash and hash functions, allowing constant-time hash updates per character.
Recommended for interviews: The KMP prefix-function solution is what most interviewers expect. It demonstrates understanding of classic string algorithms and avoids redundant comparisons. The brute force method shows you understand the definition of prefix and suffix, but the linear-time KMP solution proves you can optimize string matching problems effectively. Rolling hash is also acceptable in interviews, especially if you already know polynomial hashing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix Comparison | O(n²) | O(1) | Simple implementation or very small input sizes |
| KMP Prefix Function (LPS Array) | O(n) | O(n) | Standard interview solution for string prefix-suffix problems |
| Rolling Hash | O(n) | O(1) | Useful when hashing utilities are already implemented or when comparing multiple substrings |