# Solving Leetcode Interviews in Seconds with AI: Longest Happy Prefix


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1392" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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.  

	# Explanation
	Here's a solution to find the longest happy prefix of a string, with a focus on efficiency:

*   **KMP Prefix Table:**  We leverage the Knuth-Morris-Pratt (KMP) algorithm's prefix table (also known as the longest proper prefix suffix array or LPS array).  This table efficiently stores, for each index `i` in the string, the length of the longest proper prefix of the substring `s[0...i]` that is also a suffix of the same substring.
*   **Last Element of LPS:** The last element of the LPS array holds the length of the longest proper prefix of the entire string `s` that is also a suffix. This is exactly what we need.
*   **Extraction:** We extract the happy prefix using the length obtained from the LPS array.

*   **Time & Space Complexity:** O(n), where n is the length of the string s.

	
	# Code
	```python
	def longest_happy_prefix(s: str) -> str:
    """
    Finds the longest happy prefix of a string.

    Args:
        s: The input string.

    Returns:
        The longest happy prefix of s, or an empty string if no such prefix exists.
    """

    n = len(s)
    lps = [0] * n
    length = 0  # Length of the previous longest prefix suffix
    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

    happy_prefix_length = lps[n - 1]

    return s[:happy_prefix_length]
	```