Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1122. Longest Duplicate Substring

My accepted Python solution to LeetCode problem 1122, Longest Duplicate Substring, running in 980ms.

  • Difficulty: Hard
  • Python
  • Runtime 980ms
  • Memory 21.6MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 980ms, memory 21.6MB, accepted 2026-01-02.

python
class Solution:
    def longestDupSubstring(self, s: str) -> str:
        n = len(s)
        MOD = 2**63 - 1
        base = 31
        
        def check(length):
            if length == 0:
                return -1
            
            h = 0
            for i in range(length):
                h = (h * base + ord(s[i])) % MOD
            
            seen = {h: 0}
            base_pow = pow(base, length, MOD)
            
            for i in range(1, n - length + 1):
                h = (h * base - ord(s[i-1]) * base_pow + ord(s[i+length-1])) % MOD
                
                if h in seen:
                    return i
                seen[h] = i
            
            return -1
        
        left, right = 1, n - 1
        result = ""
        
        while left <= right:
            mid = (left + right) // 2
            idx = check(mid)
            if idx != -1:
                result = s[idx:idx+mid]
                left = mid + 1
            else:
                right = mid - 1
        
        return result

Source