#1392

Hard

LeetCode Problem Workspace

Longest Happy Prefix

Find the longest non-empty prefix of a string that also appears as its suffix, optimizing with rolling hash techniques.

string rolling hash string matching hash function

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.

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.

terminal

Solution

Solution 1: String Hashing

**String Hashing** is a method to map a string of any length to a non-negative integer, with the probability of collision being almost zero. String hashing is used to calculate the hash value of a string, which allows for quick determination of whether two strings are equal.

1

2

3

4

5

6

class Solution:
    def longestPrefix(self, s: str) -> str:
        for i in range(1, len(s)):
            if s[:-i] == s[i:]:
                return s[i:]
        return ''

Solution 2: KMP Algorithm

According to the problem description, we need to find the longest happy prefix of a string, which is the longest prefix of the string that is also a suffix of the string. We can use the KMP algorithm to solve this problem.

1

2

3

4

5

6

class Solution:
    def longestPrefix(self, s: str) -> str:
        for i in range(1, len(s)):
            if s[:-i] == s[i:]:
                return s[i:]
        return ''

Continue Practicing

#2223 sum of scores of built strings #2430 maximum deletions on a string #1461 check if a string contains all binary codes of size k