Longest Duplicate Substring
Problem Description
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
sconsists of lowercase English letters.
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
The brute force approach is to generate all possible substrings and check if more than one instance of a substring exists. Although this will work eventually, it's far from optimal. Given the nature of substrings, we can sort them and then check adjacent pairs for duplicates.
The general idea is to consider substrings of all possible lengths, starting from the longest. If we find a duplicate substring of a certain length, we record that as our longest duplicate substring.
Code:
- Time Complexity: O(n^3), where n is the length of the string. For each potential substring length, a substring comparison which in worst case can take O(n^2) time.
- Space Complexity: O(n^2), for storing all possible substrings.
2. Optimized Approach using Binary Search and Rolling Hash
Intuition:
The optimized approach uses binary search combined with a rolling hash technique to efficiently determine the longest duplicate substring.
- Binary Search: We perform a binary search on the length of the substring. Initially, set
leftas 1 andrightas n (length of string). - Rolling Hash: Pre-calculate the hash values for substrings to avoid recalculating hash values for overlapping sequences. This can be efficiently achieved using powers of a base number and modulus operations.
This method narrows down to the longest possible duplicate substring by leveraging the logarithmic exploration of the binary search and the efficiency of rolling hash.
Code:
- Time Complexity: O(n log n), where n is the length of the string. Binary search contributes a
log nfactor, and each call to check for duplicates using rolling hash is O(n). - Space Complexity: O(n), for storing hash values and their start positions in the hashmap.