1044. Longest Duplicate Substring

Description

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 * 10⁴
s consists of lowercase English letters.

Solution

longest-duplicate-substring.py

class Solution:
    def robinKarp(self, s, M):
        if M == 0: return 0

        q = (1 << 31) - 1
        h = pow(256, M - 1, q)
        d = 256
        t = 0
        mp = collections.defaultdict(list)

        for i in range(M):
            t = (t * d + ord(s[i])) % q
        mp[t].append(0)

        for i in range(len(s) - M):
            t = (d * (t - ord(s[i]) * h) + ord(s[i + M])) % q

            for j in mp[t]:
                if s[j : j + M] == s[i + 1 : i + 1 + M]:
                    return (True, s[j : j + M])
            mp[t].append(i + 1)

        return (False, '')

    def longestDupSubstring(self, s: str) -> str:
        left, right = 0, len(s)
        res = ''

        while left + 1 < right:
            mid = left + (right - left) // 2
            isFound, word = self.robinKarp(s, mid)

            if isFound:
                left, res = mid, word
            else:
                right = mid

        return res