In this guide, you will get 1392. Longest Happy Prefix LeetCode Solution with the best time and space complexity. The solution to Longest Happy Prefix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 <= 105
s contains only lowercase English letters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
1392. Longest Happy Prefix LeetCode Solution in C++
class Solution {
public:
string longestPrefix(string s) {
constexpr int kBase = 26;
constexpr long kHash = 8'417'508'174'513;
const int n = s.length();
int maxLength = 0;
long pow = 1;
long prefixHash = 0; // the hash of s[0..i]
long suffixHash = 0; // the hash of s[j..n)
for (int i = 0, j = n - 1; i < n - 1; ++i, --j) {
prefixHash = (prefixHash * kBase + val(s[i])) % kHash;
suffixHash = (val(s[j]) * pow + suffixHash) % kHash;
pow = pow * kBase % kHash;
if (prefixHash == suffixHash)
maxLength = i + 1;
}
return s.substr(0, maxLength);
}
private:
constexpr int val(char c) {
return c - 'a';
}
}; /* code provided by PROGIEZ */
1392. Longest Happy Prefix LeetCode Solution in Java
class Solution {
public String longestPrefix(String s) {
final int kBase = 26;
final long kHash = 8_417_508_174_513L;
final int n = s.length();
int maxLength = 0;
long pow = 1;
long prefixHash = 0; // the hash of s[0..i]
long suffixHash = 0; // the hash of s[j..n)
for (int i = 0, j = n - 1; i < n - 1; ++i, --j) {
prefixHash = (prefixHash * kBase + val(s.charAt(i))) % kHash;
suffixHash = (val(s.charAt(j)) * pow + suffixHash) % kHash;
pow = pow * kBase % kHash;
if (prefixHash == suffixHash)
maxLength = i + 1;
}
return s.substring(0, maxLength);
}
private int val(char c) {
return c - 'a';
}
} // code provided by PROGIEZ
1392. Longest Happy Prefix LeetCode Solution in Python
class Solution:
def longestPrefix(self, s: str) -> str:
kBase = 26
kHash = 8_417_508_174_513
n = len(s)
maxLength = 0
pow = 1
prefixHash = 0 # the hash of s[0..i]
suffixHash = 0 # the hash of s[j..n)
def val(c: str) -> int:
return ord(c) - ord('a')
j = n - 1
for i in range(n - 1):
prefixHash = (prefixHash * kBase + val(s[i])) % kHash
suffixHash = (val(s[j]) * pow + suffixHash) % kHash
pow = pow * kBase % kHash
if prefixHash == suffixHash:
maxLength = i + 1
j -= 1
return s[:maxLength] # code by PROGIEZ
