This problem requires identifying the longest happy prefix in a given string, meaning a non-empty prefix that also matches a suffix without overlapping the whole string. The most efficient methods use either a KMP-style Longest Prefix Suffix table or rolling hash string comparison. Correct handling of overlaps and avoiding false matches is key to optimizing both time and space for large inputs.
Problem Statement
Given a string s, determine the longest non-empty prefix of s which also appears as a suffix. The prefix must not be the entire string itself. If no such prefix exists, return an empty string "".
For example, for s = "level", the prefixes are "l", "le", "lev", "leve" and the suffixes are "l", "el", "vel", "evel". The longest happy prefix is "l". For s = "ababab", the longest prefix matching a suffix is "abab". Input strings consist only of lowercase English letters, and lengths range from 1 to 105.
Examples
Example 1
Input: s = "level"
Output: "l"
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"
"abab" is the largest prefix which is also suffix. They can overlap in the original string.
Constraints
- 1 <= s.length <= 105
- s contains only lowercase English letters.
Solution Approach
KMP-based Longest Prefix Suffix Table
Build a Longest Prefix Suffix (LPS) array similar to KMP preprocessing. Iterate through the string, computing the LPS values to track the longest prefix matching a suffix. Return the substring corresponding to the final LPS value. This guarantees O(n) time and O(n) space without hash collisions.
Rolling Hash Comparison
Compute prefix and suffix hashes for all substring lengths using a rolling hash function. Compare the hashes from start and end, updating the maximum matching length when hashes match. Careful modular arithmetic avoids collisions and keeps the approach efficient, achieving O(n) time with O(1) additional space for hash values.
Combined Verification Strategy
Use rolling hash to quickly identify candidate prefix-suffix matches, then verify the actual string equality to eliminate hash collision errors. This hybrid approach balances speed and accuracy, particularly for very large strings where naive substring comparison is too slow.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) using KMP or rolling hash, where n is the string length. Space complexity is O(n) for LPS array or O(1) extra for rolling hash with modular arithmetic. Verification steps do not increase asymptotic complexity but add constant time per candidate.
What Interviewers Usually Probe
- Will you consider overlaps between prefix and suffix?
- Can you implement this in linear time without extra string copies?
- Are you handling hash collisions correctly when using rolling hash?
Common Pitfalls or Variants
Common pitfalls
- Forgetting that the prefix cannot be the entire string itself.
- Miscomputing prefix and suffix hashes leading to false matches.
- Failing to account for overlapping prefix and suffix when choosing the longest match.
Follow-up variants
- Return the count of all happy prefixes instead of the longest one.
- Modify for a string with uppercase and lowercase letters, requiring case-sensitive matching.
- Determine all indices where a prefix matches a suffix throughout the string.
How GhostInterview Helps
- Automatically computes LPS or rolling hash tables to identify the longest happy prefix quickly.
- Highlights candidate prefixes and validates collisions to ensure correct output.
- Provides step-by-step insight on overlapping matches and proper substring selection.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the definition of a happy prefix in this problem?
A happy prefix is a non-empty prefix of the string that also occurs as a suffix without being the entire string.
Can rolling hash handle collisions in Longest Happy Prefix?
Yes, but verification of the actual substring is necessary to eliminate rare hash collisions for correctness.
Is this problem solvable in linear time?
Yes, using either the KMP Longest Prefix Suffix array or a rolling hash approach ensures O(n) time complexity.
How do overlaps between prefix and suffix affect the solution?
Overlaps are allowed as long as the prefix is not the full string; careful tracking ensures the longest valid prefix is returned.
What pattern does this problem primarily follow?
It follows the String plus Rolling Hash pattern, often leveraging KMP-style prefix-suffix computations for efficiency.
Need direct help with Longest Happy Prefix instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Longest Happy Prefix from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Calculate the sum of scores of built strings by analyzing longest common prefixes with suffixes in a string using efficient algorithms.
Open problem page#2430 Maximum Deletions on a StringFind the maximum number of deletions on a string using state transition dynamic programming and rolling hash techniques efficiently.
Open problem page#1461 Check If a String Contains All Binary Codes of Size KDetermine if every possible binary string of length k exists as a substring within a given binary string s efficiently using a hash set.
Open problem page