Longest Duplicate Substring

• The length of the longest duplicate substring can be anywhere from 0 to n-1. We can binary search for this length.
• Define a search space for the length, low = 1, high = n-1.
• In each step of the binary search, pick a mid length.
• Use a helper function, search(length), to check if a duplicate substring of length mid exists.
• The search(length) function uses the Rabin-Karp algorithm with a rolling hash.
  • It slides a window of size length across the string.
  • It calculates the hash of each substring in O(1) time (after an initial O(length) calculation) using the rolling hash technique.
  • A HashSet is used to store hashes of seen substrings. If a hash collision occurs, we have found a potential duplicate.
  • To be perfectly correct, upon a hash collision, one should compare the actual substrings to rule out false positives, though with a large prime modulus, this is rare.
• If search(mid) finds a duplicate, we know a solution of at least length mid is possible. We store this potential answer and try for a longer one by setting low = mid + 1.
• If search(mid) finds no duplicate, the length mid is too long. We must try a shorter one by setting high = mid - 1.
• The final answer is the longest valid substring found during the search.

We can binary search for the answer, which is the length of the substring. The search space for the length L is [0, n-1]. For a given L, we need to efficiently check if there's any repeated substring of that length. This check can be performed in O(n) time using a rolling hash.

The rolling hash technique allows us to calculate the hash of a new substring from the previous one in O(1) time. We slide a window of length L over the string. We store the hashes of the substrings we've seen in a HashSet. If we compute a hash that's already in the set, we've likely found a duplicate. We then verify it's a true duplicate (not a hash collision) and proceed with the binary search.

If a duplicate of length mid is found, we know we might be able to do better, so we search in the upper half (low = mid + 1). If not, mid is too large, and we search in the lower half (high = mid - 1).

1import java.util.HashSet;2 3class Solution {4    // Using prefix hashes for O(1) hash calculation of any substring5    public String longestDupSubstring(String S) {6        int n = S.length();7        int low = 1, high = n;8        String result = "";9 10        while (low <= high) {11            int mid = low + (high - low) / 2;12            String duplicate = search(S, mid);13            if (duplicate != null) {14                result = duplicate;15                low = mid + 1;16            } else {17                high = mid - 1;18            }19        }20        return result;21    }22 23    private String search(String s, int len) {24        long prime = 29;25        long power = 1;26        for (int i = 0; i < len; i++) {27            power = (power * prime);28        }29 30        HashSet<Long> seen = new HashSet<>();31        long currentHash = 0;32        for (int i = 0; i < s.length(); i++) {33            currentHash = (currentHash * prime) + (s.charAt(i) - 'a');34            if (i >= len) {35                currentHash -= (long)(s.charAt(i - len) - 'a') * power;36            }37            if (i >= len - 1) {38                if (seen.contains(currentHash)) {39                    // For this problem, simple hash check is often sufficient.40                    // A robust solution would verify the substring match here.41                    return s.substring(i - len + 1, i + 1);42                }43                seen.add(currentHash);44            }45        }46        return null;47    }48}

• Initialize an empty string longestDup to store the result.
• Iterate through all possible substring lengths len from n-1 down to 1.
• For each len, create a HashSet to store unique substrings of that length encountered so far.
• Iterate through the string s from index i = 0 to n - len.
• Extract the substring sub of length len starting at i.
• Try to add sub to the HashSet. If the add method returns false, it means sub is a duplicate.
• Since we are iterating from the longest possible length downwards, the first duplicate we find is the answer. Return it immediately.
• If the loops complete without finding any duplicates, return an empty string.

The brute-force method checks for duplicates for every possible substring length. We can start by checking for a duplicate of length n-1, then n-2, and so on, down to 1. For a fixed length L, we can iterate through the string and extract all substrings of length L. A HashSet is used to keep track of the substrings of length L that we have seen. If we encounter a substring that is already in the set, we have found a duplicate of length L. Since we are checking from the largest length downwards, the first one we find will be the longest possible, and we can return it immediately.

1import java.util.HashSet;2 3public class Solution {4    public String longestDupSubstring(String s) {5        int n = s.length();6        for (int len = n - 1; len > 0; len--) {7            HashSet<String> seen = new HashSet<>();8            for (int i = 0; i <= n - len; i++) {9                String sub = s.substring(i, i + len);10                if (seen.contains(sub)) {11                    return sub;12                }13                seen.add(sub);14            }15        }16        return "";17    }18}

This approach is too slow because of the nested loops and the overhead of creating and hashing substrings repeatedly.

• Construct the Suffix Array (sa) for the input string s. The suffix array is an array of integers that gives the starting positions of all suffixes of s in lexicographical (alphabetical) order. This can be done using algorithms like Manber-Myers in O(n log^2 n) or O(n log n) time.
• From the Suffix Array, construct the LCP (Longest Common Prefix) Array. The lcp[i] stores the length of the longest common prefix between the suffixes sa[i-1] and sa[i]. Kasai's algorithm can build the LCP array in O(n) time given the suffix array.
• The longest duplicated substring in s corresponds to the longest common prefix between any two suffixes of s. When suffixes are sorted, the longest common prefixes will be between adjacent suffixes.
• Therefore, the length of the longest duplicated substring is simply the maximum value in the LCP array.
• Find the maximum value maxLength in the LCP array and the index maxIndex where it occurs.
• The result is the substring of s starting at index sa[maxIndex] with length maxLength.
• If the maximum LCP value is 0, no duplicates exist, so return an empty string.

This approach transforms the problem from finding substrings to analyzing suffixes.

1. Suffix Array (sa): We first build a suffix array for the string s. This array contains the starting indices of all suffixes of s, sorted alphabetically. For example, for s = "banana", the sorted suffixes are "a", "ana", "anana", "banana", "na", "nana". The suffix array would be [5, 3, 1, 0, 4, 2].

2. LCP Array: Next, we build the LCP array. lcp[i] is the length of the longest common prefix between the i-1-th and i-th suffixes in the sorted order (i.e., LCP of suffix starting at sa[i-1] and sa[i]). For our "banana" example, the LCP array would be [0, 1, 3, 0, 2, 2] (values may vary slightly based on definition). The LCP between "ana" (from sa[1]=3) and "anana" (from sa[2]=1) is "ana", which has length 3.

3. Find Max LCP: The longest duplicated substring is the one corresponding to the largest value in the LCP array. In our example, the max LCP is 3. This tells us the longest duplicate has length 3. We can find the substring itself ("ana") from the suffix array at the index where the max LCP was found.

While extremely powerful, implementing suffix array and LCP array construction is non-trivial. Below is a conceptual code structure, as a full implementation is quite lengthy.

1// Conceptual code. Full implementation is complex.2class SuffixArraySolution {3    public String longestDupSubstring(String s) {4        int n = s.length();5 6        // 1. Build Suffix Array for s. This is a complex algorithm.7        int[] sa = buildSuffixArray(s, n);8 9        // 2. Build LCP Array from Suffix Array and s (e.g., using Kasai's Algorithm).10        int[] lcp = buildLCPArray(s, sa, n);11 12        // 3. Find the maximum value in the LCP array.13        int maxLength = 0;14        int startIndex = 0;15        for (int i = 0; i < n; i++) {16            if (lcp[i] > maxLength) {17                maxLength = lcp[i];18                startIndex = sa[i];19            }20        }21 22        // 4. Return the longest duplicate substring found.23        return s.substring(startIndex, startIndex + maxLength);24    }25 26    private int[] buildSuffixArray(String s, int n) {27        // ... O(n log n) or O(n log^2 n) implementation ...28        return new int[n];29    }30 31    private int[] buildLCPArray(String s, int[] sa, int n) {32        // ... O(n) Kasai's algorithm implementation ...33        return new int[n];34    }35}