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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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: |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,177 views views
Watch 9 more video solutions →Practice Longest Happy Prefix with our built-in code editor and test cases.
Practice on FleetCode