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.The goal is to find the longest prefix of a string that is also its suffix, excluding the entire string itself. A naive comparison of all prefixes and suffixes leads to O(n^2) time, which is inefficient for long strings. Instead, efficient string matching techniques can be used.
A common strategy is based on the KMP (Knuth–Morris–Pratt) prefix function. By building the LPS (Longest Prefix Suffix) array, we track for each position the length of the longest prefix that also appears as a suffix up to that index. The final value in this array directly indicates the length of the longest happy prefix.
Another method uses rolling hash. As we scan the string, we compute prefix and suffix hashes simultaneously and compare them to detect matches efficiently. This avoids explicit substring comparisons.
Both techniques reduce the problem to O(n) time while using minimal additional memory, making them well suited for large input strings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| KMP Prefix Function (LPS) | O(n) | O(n) |
| Rolling Hash | O(n) | O(1) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Use Longest Prefix Suffix (KMP-table) or String Hashing.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of prefix-suffix string problems appear in technical interviews at large tech companies. Interviewers often expect knowledge of KMP, hashing, or other efficient string matching techniques.
The optimal approach uses the KMP prefix function (LPS array). It efficiently tracks the longest prefix that is also a suffix for each position in the string, allowing the final value to determine the answer in linear time.
Yes, a rolling hash technique can compare prefix and suffix hashes while scanning the string. When both hashes match at a position, it indicates a candidate happy prefix. This approach also runs in O(n) time.
String matching algorithms like KMP are best suited for this problem. The prefix function helps reuse previously computed information about matching prefixes and suffixes, avoiding repeated comparisons.