# Longest Duplicate Substring
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-duplicate-substring)
Canonical: https://scaleengineer.com/dsa/problems/longest-duplicate-substring
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** String, Suffix Array
**Companies:** [Coupang](https://scaleengineer.com/companies/coupang)
---
## Problem
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 * 104`
* `s` consists of lowercase English letters.

# Approaches
## Brute Force with HashSet
This approach involves systematically generating all possible substrings and using a `HashSet` to identify duplicates. We iterate through all possible lengths for a duplicate substring, from longest to shortest. For each length, we generate all substrings of that length and use a set to find the first occurrence of a duplicate.
**Time:** O(n^3). We have a loop for the length `len` from `n-1` down to 1 (`O(n)`). Inside it, another loop for the starting position `i` (`O(n)`). The `substring()` operation takes `O(len)` time, and `HashSet` operations (hashing and comparison) also take `O(len)`. This results in a total complexity of roughly `O(n * n * n) = O(n^3)`. · **Space:** O(n^2). In the worst-case scenario for a given length `L`, the `HashSet` might need to store `n-L+1` unique substrings. The total space for substrings of length `L` would be `(n-L+1) * L`, which can be up to `O(n^2)`.
**Pros:** Simple to understand and conceptualize.; Straightforward to implement.
**Cons:** Extremely inefficient in terms of both time and space.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.; The space complexity can be very high as it needs to store many substrings.
### Explanation
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.

```java
import java.util.HashSet;

public class Solution {
    public String longestDupSubstring(String s) {
        int n = s.length();
        for (int len = n - 1; len > 0; len--) {
            HashSet<String> seen = new HashSet<>();
            for (int i = 0; i <= n - len; i++) {
                String sub = s.substring(i, i + len);
                if (seen.contains(sub)) {
                    return sub;
                }
                seen.add(sub);
            }
        }
        return "";
    }
}
```
This approach is too slow because of the nested loops and the overhead of creating and hashing substrings repeatedly.
### Algorithm
*   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.

## Binary Search on Length with Rabin-Karp
A much more efficient approach uses binary search on the length of the substring combined with the Rabin-Karp algorithm for string matching. The problem has a monotonic property: if a duplicate substring of length `k` exists, a duplicate of any length less than `k` also exists. This allows us to binary search for the optimal length. For each candidate length, we use a rolling hash to efficiently check for duplicates in linear time.
**Time:** O(n log n). The binary search performs `O(log n)` iterations. Inside each iteration, the `search` function using rolling hash takes `O(n)` time to check for duplicates of a given length. · **Space:** O(n). The `HashSet` used in the `search` function can store up to `O(n)` distinct hashes in the worst case.
**Pros:** Significantly more efficient with O(n log n) time complexity.; Fast enough to pass the given constraints.; A standard and powerful technique for optimization problems.
**Cons:** More complex to implement than the brute-force approach.; Requires understanding of binary search and hashing (Rabin-Karp).; Hash collisions are a potential issue, which might require verification or using multiple hash functions (double hashing) for robustness.
### Explanation
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`).

```java
import java.util.HashSet;

class Solution {
    // Using prefix hashes for O(1) hash calculation of any substring
    public String longestDupSubstring(String S) {
        int n = S.length();
        int low = 1, high = n;
        String result = "";

        while (low <= high) {
            int mid = low + (high - low) / 2;
            String duplicate = search(S, mid);
            if (duplicate != null) {
                result = duplicate;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }

    private String search(String s, int len) {
        long prime = 29;
        long power = 1;
        for (int i = 0; i < len; i++) {
            power = (power * prime);
        }

        HashSet<Long> seen = new HashSet<>();
        long currentHash = 0;
        for (int i = 0; i < s.length(); i++) {
            currentHash = (currentHash * prime) + (s.charAt(i) - 'a');
            if (i >= len) {
                currentHash -= (long)(s.charAt(i - len) - 'a') * power;
            }
            if (i >= len - 1) {
                if (seen.contains(currentHash)) {
                    // For this problem, simple hash check is often sufficient.
                    // A robust solution would verify the substring match here.
                    return s.substring(i - len + 1, i + 1);
                }
                seen.add(currentHash);
            }
        }
        return null;
    }
}
```
### Algorithm
*   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.

## Suffix Array and LCP Array
A highly efficient and classic approach for this type of string problem involves advanced data structures: the Suffix Array and the LCP (Longest Common Prefix) Array. The core idea is that any duplicated substring is a common prefix of at least two suffixes of the original string. By sorting all suffixes lexicographically, we can easily find the longest common prefixes between adjacent suffixes, and the maximum of these is our answer.
**Time:** O(n log n). The main bottleneck is the construction of the suffix array, which typically takes `O(n log n)` or `O(n log^2 n)`. Building the LCP array with Kasai's algorithm is a subsequent `O(n)` step. · **Space:** O(n). Space is required to store the suffix array, the LCP array, and auxiliary arrays used during their construction.
**Pros:** Asymptotically very efficient, with a time complexity of O(n log n).; A fundamental and powerful tool in string algorithms, applicable to a wide range of problems.; Guaranteed to be correct and does not suffer from issues like hash collisions.
**Cons:** Very complex to implement from scratch, especially under time constraints like in an interview or contest.; The constant factors in the time complexity can be large, making it potentially slower than a well-implemented Rabin-Karp approach for some inputs, despite the same asymptotic complexity.
### Explanation
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.

```java
// Conceptual code. Full implementation is complex.
class SuffixArraySolution {
    public String longestDupSubstring(String s) {
        int n = s.length();

        // 1. Build Suffix Array for s. This is a complex algorithm.
        int[] sa = buildSuffixArray(s, n);

        // 2. Build LCP Array from Suffix Array and s (e.g., using Kasai's Algorithm).
        int[] lcp = buildLCPArray(s, sa, n);

        // 3. Find the maximum value in the LCP array.
        int maxLength = 0;
        int startIndex = 0;
        for (int i = 0; i < n; i++) {
            if (lcp[i] > maxLength) {
                maxLength = lcp[i];
                startIndex = sa[i];
            }
        }

        // 4. Return the longest duplicate substring found.
        return s.substring(startIndex, startIndex + maxLength);
    }

    private int[] buildSuffixArray(String s, int n) {
        // ... O(n log n) or O(n log^2 n) implementation ...
        return new int[n];
    }

    private int[] buildLCPArray(String s, int[] sa, int n) {
        // ... O(n) Kasai's algorithm implementation ...
        return new int[n];
    }
}
```
### Algorithm
*   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.

# Solutions
### Java

```java
class Solution {
private
  long[] p;
private
  long[] h;
public
  String longestDupSubstring(String s) {
    int base = 131;
    int n = s.length();
    p = new long[n + 10];
    h = new long[n + 10];
    p[0] = 1;
    for (int i = 0; i < n; ++i) {
      p[i + 1] = p[i] * base;
      h[i + 1] = h[i] * base + s.charAt(i);
    }
    String ans = "";
    int left = 0, right = n;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      String t = check(s, mid);
      if (t.length() > 0) {
        left = mid;
        ans = t;
      } else {
        right = mid - 1;
      }
    }
    return ans;
  }
private
  String check(String s, int len) {
    int n = s.length();
    Set<Long> vis = new HashSet<>();
    for (int i = 1; i + len - 1 <= n; ++i) {
      int j = i + len - 1;
      long t = h[j] - h[i - 1] * p[j - i + 1];
      if (vis.contains(t)) {
        return s.substring(i - 1, j);
      }
      vis.add(t);
    }
    return "";
  }
}

```

### CPP

```cpp
typedef unsigned long long ULL ; class Solution { public: ULL p [ 30010 ]; ULL h [ 30010 ]; string longestDupSubstring ( string s ) { int base = 131 , n = s . size (); p [ 0 ] = 1 ; for ( int i = 0 ; i < n ; ++ i ) { p [ i + 1 ] = p [ i ] * base ; h [ i + 1 ] = h [ i ] * base + s [ i ]; } int left = 0 , right = n ; string ans = "" ; while ( left < right ) { int mid = ( left + right + 1 ) >> 1 ; string t = check ( s , mid ); if ( t . empty ()) right = mid - 1 ; else { left = mid ; ans = t ; } } return ans ; } string check ( string & s , int len ) { int n = s . size (); unordered_set < ULL > vis ; for ( int i = 1 ; i + len - 1 <= n ; ++ i ) { int j = i + len - 1 ; ULL t = h [ j ] - h [ i - 1 ] * p [ j - i + 1 ]; if ( vis . count ( t )) return s . substr ( i - 1 , len ); vis . insert ( t ); } return "" ; } };
```

### Python

```python
class Solution:
    def longestDupSubstring(self, s: str) -> str: def check(l): vis = set() for i in range(n - l + 1): t = s[i: i + l] if t in vis: return t vis . add(t) return '' n = len(s) left, right = 0, n ans = '' while left < right: mid = (left + right + 1) >> 1 t = check(mid) ans = t or ans if t: left = mid else: right = mid - 1 return ans

```