We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Happy Prefix

Difficulty: Hard

Problem Description

A string is called a happy prefix if it 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.

Key Insights

  • A happy prefix must be a non-empty substring that can be found at both the start and end of the string.
  • The longest happy prefix can be found by examining the overlaps between the prefix and suffix of the string.
  • Efficient algorithms such as KMP (Knuth-Morris-Pratt) can be utilized to find the longest prefix which is also a suffix.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem of finding the longest happy prefix, we can employ the KMP algorithm's preprocessing step. The algorithm builds a longest prefix-suffix (LPS) array that helps in identifying the longest prefix that is also a suffix efficiently.

  1. Create an array lps where lps[i] represents the length of the longest proper prefix which is also a suffix for the substring s[0..i].
  2. Iterate through the string to fill the lps array.
  3. The value lps[n-1] (where n is the length of the string) gives us the length of the longest happy prefix.
  4. Return the substring of s from the start with length equal to lps[n-1].

Code Solutions

def longest_happy_prefix(s: str) -> str:
    n = len(s)
    lps = [0] * n
    length = 0
    i = 1

    while i < n:
        if s[i] == s[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    # The longest happy prefix length
    happy_length = lps[-1]
    return s[:happy_length]  # Return the longest happy prefix
← Back to All Questions