class Solution:
    def longestDupSubstring(self, s: str) -> str:
        # --- PART 1: The Setup (Math constants) ---
        nums = [ord(c) - ord('a') for c in s]
        MOD = 2**63 - 1  # Big prime number to avoid collisions
        BASE = 26        # 26 lowercase letters
        n = len(s)

        # --- PART 2: The "Check" Function (Rabin-Karp) ---
        # Returns start index if found, -1 if not
        def search(length):
            # 1. Compute hash of the FIRST window (0 to length-1)
            current_hash = 0
            for i in range(length):
                current_hash = (current_hash * BASE + nums[i]) % MOD
            
            seen = {current_hash}
            
            # Constant needed to remove the leading character: BASE^(L-1)
            # This is the value of the "highest place" in our number system
            highest_pow = pow(BASE, length - 1, MOD)
            
            # 2. Rolling Update (The "O(1)" magic)
            for i in range(1, n - length + 1):
                # Logic: (Current - Leading_Char_Value) * Base + New_Char_Value
                
                # Remove leading char (previous window's first char)
                # We add MOD to ensure the result isn't negative before modulo
                current_hash = (current_hash - nums[i-1] * highest_pow) % MOD
                
                # Shift left and add new trailing char
                current_hash = (current_hash * BASE + nums[i + length - 1]) % MOD
                
                if current_hash in seen:
                    return i
                seen.add(current_hash)
                
            return -1

        # --- PART 3: The Driver (Binary Search on Answer) ---
        # Exactly the same logic as Koko Eating Bananas / Ship Packages
        left, right = 1, n - 1
        start_index = -1
        
        while left <= right:
            mid = (left + right) // 2
            found = search(mid)
            
            if found != -1:
                start_index = found # Valid! Save it.
                left = mid + 1      # Try for longer
            else:
                right = mid - 1     # Impossible. Try shorter.
                
        return s[start_index : start_index + (left - 1)] if start_index != -1 else ""