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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Happy Prefix

Number: 1508

Difficulty: Hard

Paid? No

Companies: Amazon, Google

Problem Description

Given a string s, find the longest "happy prefix". A happy prefix is defined as a non-empty prefix which is also a suffix of s, excluding the string itself. If no such prefix exists, return an empty string.

Key Insights

  • The problem can be solved efficiently by leveraging techniques used in string matching algorithms.
  • A key method is to compute the prefix function (also known as pi array) from the KMP (Knuth-Morris-Pratt) algorithm.
  • The value at the last index of the pi array corresponds to the length of the longest prefix that is also a suffix (excluding the whole string).
  • An alternative approach is to use a rolling hash technique, but the KMP prefix function is more straightforward and has a linear time complexity.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s
Space Complexity: O(n), for storing the prefix function

Solution

We use the KMP prefix function to solve this problem:

  1. Initialize an array pi of size n (length of s) with zeros.
  2. Iterate through the string from the second character, and update the pi array which keeps track of the longest proper prefix which is also a suffix for each substring ending at that index.
  3. The value at pi[n-1] gives the length of the longest happy prefix.
  4. Return the substring from the beginning of s up to that length. The algorithm ensures that we only traverse the string once with extra space proportional to n.

Code Solutions

# Function to compute the longest happy prefix using KMP prefix function
def longestHappyPrefix(s: str) -> str:
    n = len(s)
    # pi[i] will hold the length of the longest prefix which is also suffix ending at i
    pi = [0] * n
    # k: length of current longest prefix-suffix
    k = 0
    # iterate from second character to build the pi array
    for i in range(1, n):
        # if the current character doesn't match, fallback using pi array
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]
        # if there is a match, extend the prefix-suffix length
        if s[i] == s[k]:
            k += 1
            pi[i] = k
        else:
            pi[i] = 0
    # pi[n-1] gives the length of the longest happy prefix
    return s[:pi[-1]]

# Example usage:
print(longestHappyPrefix("level"))    # Output: "l"
print(longestHappyPrefix("ababab"))   # Output: "abab"
← Back to All Questions