Longest Happy Prefix - Solution & Explanation
Problem Statement
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 <= 105scontains only lowercase English letters.
Approach Overview
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 1: KMP Algorithm
The KMP (Knuth-Morris-Pratt) algorithm is an efficient string matching algorithm that includes preprocessing the pattern (or string in this case) to construct a partially matched table, which can be utilized to identify proper prefixes which are also suffixes.
By utilizing this table, we can find the longest happy prefix by examining the last value of this table.
This C solution uses the KMP algorithm's prefix function table computation to determine the longest happy prefix. The helper function computeLPSArray constructs the prefix table for the given string, and then the last value in this table gives us the length of the longest prefix which is a suffix.
Code
C
C++
Java
Python
C#
JavaScript
Go
TypeScript
Complexity
Time Complexity: O(n), where n is the length of the string, due to the KMP preprocessing step.
Space Complexity: O(n) for the LPS table.
Approach 2: Rolling Hash
This approach leverages computation of hash values to dynamically relate prefixes and suffixes. We incrementally maintain prefix hash and suffix hash values following pattern matching principles. Equal hashes upon completion indicate potential matching of prefix and suffix. This strategy takes advantage of properties of polynomial rolling hashes.
This solution utilizes a rolling hash to compute prefix and suffix hashes dynamically. It maintains a modular base for polynomial hash calculations to ensure numerical stability. When the prefix and suffix hash values are identical, the length of the matching substring is updated.
Complexity
Time Complexity: O(n), reflecting the single pass over the string.
Space Complexity: O(1) as space is only used for hashes and scalar variables.
Approach 3: 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.
We choose a fixed value BASE, and consider the string as a number in BASE radix, assigning a value greater than 0 to represent each character. Generally, the values we assign are much smaller than BASE. For example, for strings composed of lowercase letters, we can assign a=1, b=2, ..., z=26. We choose a fixed value MOD, and calculate the remainder of the BASE radix number divided by MOD, which is used as the hash value of the string.
Generally, we choose BASE=131 or BASE=13331, at which point the probability of hash value collision is extremely low. As long as the hash values of two strings are the same, we consider the two strings to be equal. Usually, MOD is chosen as 2^{64}. In C++, we can directly use the unsigned long long type to store this hash value. When calculating, we do not handle arithmetic overflow. When overflow occurs, it is equivalent to automatically taking the modulus of 2^{64}, which can avoid inefficient modulus operations.
Except for extremely specially constructed data, the above hash algorithm is unlikely to produce collisions. In general, the above hash algorithm can appear in the standard answers of the problem. We can also choose some appropriate values of BASE and MOD (such as large prime numbers), and perform several groups of hash operations. Only when the results are all the same do we consider the original strings to be equal, making it even more difficult to construct data that causes this hash to produce errors.
Complexity Comparison
| Approach | Complexity |
|---|---|
| KMP Algorithm | Time Complexity: |
| Rolling Hash | Time Complexity: |
| String Hashing | — |
Detailed Complexity Analysis
| 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 |
Video Solution
KMP Algorithm - Longest Happy Prefix | Covering ALL DSA Patterns in Coding Interviews • Bharat Khanna • 4,970 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Happy Prefix easy or hard?
Longest Happy Prefix Python/Java solution
How to solve Longest Happy Prefix in O(n)?
What is the best approach for Longest Happy Prefix?
Is Longest Happy Prefix asked at Google/Amazon/Meta?
What data structure is used in Longest Happy Prefix?
What is the time complexity of Longest Happy Prefix?
Ready to solve this problem?
Practice Longest Happy Prefix with our built-in code editor and test cases.
Practice on FleetCode