LeetCode 1044: Longest Duplicate Substring Solution

Master LeetCode problem 1044 (Longest Duplicate Substring), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1044. Longest Duplicate Substring

Hard

String Binary Search Sliding Window Rolling Hash Suffix Array Hash Function

Problem Explanation

Explanation

To solve this problem, we can use binary search along with the Rabin-Karp algorithm. We will consider different substring lengths and for each length, we will check if there exists a duplicate substring of that length. The Rabin-Karp algorithm helps us efficiently check if two substrings of a given length are equal in constant time. We will keep track of the seen substrings using a HashSet. By binary searching on the possible lengths of the substrings, we can find the longest duplicate substring.

Time Complexity: O(N*log(N)), where N is the length of the input string.
Space Complexity: O(N)

Solution Code

class Solution {
    public String longestDupSubstring(String s) {
        int left = 1, right = s.length() - 1;
        String result = "";
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            String dupStr = searchForDuplicateSubstring(s, mid);
            
            if (dupStr.length() > result.length()) {
                result = dupStr;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    private String searchForDuplicateSubstring(String s, int len) {
        long base = 26;
        long mod = (long)Math.pow(2, 32);
        long hash = 0;
        
        for (int i = 0; i < len; i++) {
            hash = (hash * base + s.charAt(i) - 'a') % mod;
        }
        
        Set<Long> seen = new HashSet<>();
        seen.add(hash);
        
        long baseLen = 1;
        for (int i = 1; i < len; i++) {
            baseLen = (baseLen * base) % mod;
        }
        
        for (int i = 1; i <= s.length() - len; i++) {
            hash = (hash * base - baseLen * (s.charAt(i - 1) - 'a') + (s.charAt(i + len - 1) - 'a')) % mod;
            if (hash < 0) {
                hash += mod;
            }
            
            if (seen.contains(hash)) {
                return s.substring(i, i + len);
            }
            
            seen.add(hash);
        }
        
        return "";
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1044 (Longest Duplicate Substring)?

This page provides optimized solutions for LeetCode problem 1044 (Longest Duplicate Substring) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1044 (Longest Duplicate Substring)?

The time complexity for LeetCode 1044 (Longest Duplicate Substring) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1044 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1044 in Java, C++, or Python.

Back to LeetCode Solutions