1392. Longest Happy Prefix LeetCode Solution

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.

Problem Statement
Complexity Analysis
Longest Happy Prefix solution in C++
Longest Happy Prefix solution in Java
Longest Happy Prefix solution in Python
Additional Resources

1392. Longest Happy Prefix LeetCode Solution image

Problem Statement of Longest Happy Prefix

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