Longest Duplicate Substring - Leetcode Solution

The Longest Duplicate Substring problem on LeetCode asks us to find the longest substring of a given string that appears at least twice. This problem can be solved using binary search and rolling hash.

Algorithm:

1. First, we create a hash function that takes a string as input and outputs its hash value. Here, we use the Rabin-Karp hash function that takes a string and a prime number as inputs and returns its hash value. The hash function is given below:

   def hash(text, prime): num = ord(text[0]) p_pow = 1 h = num for char in text[1:]: num = ord(char) p_pow = (p_pow * prime) % MOD h = (h * prime + num) % MOD return h

   Here, MOD is a large prime number that we use to avoid hash collisions.

2. Next, we use binary search to find the length of the longest duplicate substring. We initialize two pointers, l and r, where l is the minimum length of the substring and r is the maximum length of the substring. We start with l=0 and r=len(s)-1 and keep halving the range until we get the length of the longest duplicate substring.

   While l <= r: mid = (l + r) // 2 if is_duplicate(s, mid): l = mid + 1 else: r = mid - 1

   Here, is_duplicate is a helper function that takes a string s and an integer length and returns True if there exists a duplicate substring of length length in s. The function is_duplicate is given below.

   def is_duplicate(s, length): hash_set = set() hash_val = hash(s[:length], PRIME) hash_set.add(hash_val) p_pow = pow(PRIME, length-1, MOD) for i in range(length, len(s)): hash_val = ((hash_val - ord(s[i-length]) * p_pow) * PRIME + ord(s[i])) % MOD if hash_val in hash_set: return True hash_set.add(hash_val) return False

3. Finally, we return the substring of length l-1 that appears at least twice in the given string s. If no such substring exists, we return an empty string.

   def longestDupSubstring(s): l, r = 0, len(s) - 1 ans = "" while l <= r: mid = (l + r) // 2 if is_duplicate(s, mid): ans = s[:mid] l = mid + 1 else: r = mid - 1 return ans

1