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.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.
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.
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.
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.
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 | Complexity |
|---|---|
| KMP Algorithm | Time Complexity: |
| Rolling Hash | Time Complexity: |
| 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 |
5 Longest Happy Prefix | String Matching • Aditya Verma • 6,383 views views
Watch 8 more video solutions →Practice Longest Happy Prefix with our built-in code editor and test cases.
Practice on FleetCode