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, 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

    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]