PPractick

The problem

You're working on a DNA/genome sequence analysis tool (or, more relatably, a log-deduplication system for compressed network packets). A "happy prefix" of a string is defined as a prefix that is also a suffix, but is not the entire string itself (no full overlap). Your task: given a string s, return the longest happy prefix. If no such prefix exists, return an empty string.

Example: s = "level" → the longest happy prefix is "l" (since "l" is both a prefix and a suffix of "level", and no longer prefix qualifies — "leve" is a prefix but not a suffix).

Function signature

string longestHappyPrefix(string s);

Test cases

Input s	Output	Explanation
"level"	"l"	"l" is prefix & suffix; "le", "lev", "leve" aren't suffixes too
"ababab"	"abab"	"abab" is both prefix and suffix, longest such match
"leetcodeleet"	"leet"	"leet" appears as both prefix and suffix
"a"	""	Single char — prefix would equal the whole string, not allowed
"aaaa"	"aaa"	"aaa" is prefix & suffix, can't use full "aaaa" (that's the whole string)
"abcabcabc"	"abcabc"	Longest non-trivial prefix=suffix match
"abcdefg"	""	No prefix matches any suffix

How interviewers phrase it

• "Given a string, find the longest prefix that is also a suffix, but isn't the whole string."
• "What's the longest string that is both a proper prefix and proper suffix of s?"
• This is LeetCode 1392 — interviewers sometimes use the exact LeetCode title "Longest Happy Prefix" if they expect you've seen it, so be ready to derive it from scratch if you haven't.

Clarifying questions to ask

1. Does "prefix" and "suffix" here mean proper (i.e., not equal to the full string)? (Yes — this is the "non-overlapping" / "happy" constraint mentioned in the prompt.)
2. Can the prefix and suffix overlap in terms of their index ranges within s (e.g., for "aaaa", prefix "aaa" (indices 0-2) and suffix "aaa" (indices 1-3) overlap in index range — is that allowed)? — Yes, index overlap is fine; only full-string overlap (proper-ness) is disallowed. This is a common point of confusion, good to clarify explicitly.
3. What should be returned if no happy prefix exists — empty string or some sentinel value?
4. What's the input size constraint? (If large, signals need for O(n) KMP-based solution over brute force.)
5. Case-sensitive comparison? Any character set constraints?

Follow-ups to expect

1. "Can you do this in O(n) instead of O(n²)?"
2. "What if you need to return ALL happy prefixes, not just the longest?"
3. "Can you solve this with the Z-function instead of KMP's LPS array?"
4. "What if input string could be huge (1e7 length) — any space optimization?"
5. "How does this relate to KMP pattern matching?"

Related questions

• Minimum characters to make string palindrome Hard
• Longest palindromic subsequence Hard
• Minimum insertions to make string palindrome Hard
• KMP Algorithm or LPS array Hard
• Shortest Palindrome Hard
• Letter Combinations of a Phone Number Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in