Introduction

In this blog post, we will explore how to solve the LeetCode problem "1044" 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

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap. Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is "". Example 1: Input: s = "banana" Output: "ana" Example 2: Input: s = "abcd" Output: "" Constraints: 2 <= s.length <= 3 * 104 s consists of lowercase English letters.

Explanation

Here's a breakdown of the approach, followed by the Python code:

• Binary Search for Length: The core idea is to use binary search to efficiently find the length of the longest duplicated substring. We binary search on the possible lengths of the substring (from 1 to len(s) - 1).
• Rabin-Karp for Substring Detection: For a given length mid (the guess from the binary search), we use the Rabin-Karp algorithm with a rolling hash to quickly check if there exists a duplicated substring of length mid. The rolling hash allows us to compute the hash of the next substring in O(1) time given the hash of the previous substring.

• Set for Duplication Check: We use a set to keep track of the hash values of the substrings we've encountered. If we find a hash value already in the set, it means we've found a duplicated substring of length mid.

• Runtime Complexity: O(n log n), where n is the length of the input string s. The binary search contributes the log n factor, and the Rabin-Karp algorithm takes O(n) time in the worst case for a given substring length. Storage Complexity: O(n) in the worst case due to the hash set.

Code

    def longestDupSubstring(s: str) -> str:
    """
    Finds the longest duplicated substring in a given string.

    Args:
        s: The input string.

    Returns:
        The longest duplicated substring.
    """

    n = len(s)
    low = 1
    high = n - 1
    longest_dup = ""

    while low <= high:
        mid = (low + high) // 2
        dup = find_dup_substring(s, mid)

        if dup:
            longest_dup = dup
            low = mid + 1  # Try for longer substring
        else:
            high = mid - 1  # Try for shorter substring

    return longest_dup


def find_dup_substring(s: str, length: int) -> str:
    """
    Checks if there exists a duplicated substring of a given length.

    Args:
        s: The input string.
        length: The length of the substring to check.

    Returns:
        A duplicated substring of the given length, or an empty string if none exists.
    """

    n = len(s)
    if length == 0:
        return ""

    # Rabin-Karp Rolling Hash
    base = 26  # Number of characters (lowercase English letters)
    modulus = 2**32  # Large prime number to avoid collisions

    h = 0
    for i in range(length):
        h = (h * base + (ord(s[i]) - ord('a'))) % modulus

    seen = {h}
    base_L = pow(base, length - 1, modulus)

    for i in range(1, n - length + 1):
        h = (h - (ord(s[i-1]) - ord('a')) * base_L) % modulus
        h = (h * base + (ord(s[i + length - 1]) - ord('a'))) % modulus
        h = (h + modulus) % modulus  # Ensure h is non-negative

        if h in seen:
            return s[i:i + length]

        seen.add(h)

    return ""