Problem Description

The problem requires us to find the longest duplicated substring within a given string s; these are substrings that appear more than once. A substring is considered a consecutive sequence of characters within the string. The key challenge here is handling the potential overlap of occurrences—this means that the same characters can be part of different duplicated substrings as long as those substrings start at different positions in s.

For example, in the string "banana", the substring "ana" is duplicated with overlapping occurrences: "banana" contains "ana" starting at the second character and again starting at the fourth character.

If no such substring exists, our function should return an empty string. The desired solution can be any one of the longest duplicated substrings if there are multiple with the same maximum length.

Intuition

The intuition behind the solution involves a [binary search](/problems/binary-search-speedrun) algorithm combined with a rolling hash technique or a hash set to quickly check for duplicate substrings.

Binary search is used to reduce the search space for the length of the longest duplicated substring. Instead of checking every possible length, we can start in the middle of the possible range of lengths and then increase or decrease our search based on whether we find a duplicate of that length.

Hash sets are used to store previously seen substrings of a certain length. As we increase or decrease the length of substrings we are looking at, we can add these to the set or check against it to see if we have seen them before. If a substring is already in the set, it means we've found a duplicate.

The process works as follows:

• We define left as the minimum length of the substring and right as the maximum possible length of a duplicated substring, which is n - 1 (where n is the length of the input string).
• We use binary search to find the largest mid value such that mid is the length of a possible duplicated substring. We check if there is a duplicate substring of this length using the helper function check.
• The check function iterates through all possible substrings of length l (where l is the current midpoint of the binary search), adding them to a hash set or returning one immediately if a duplicate is found.

In this solution, we leverage the efficiency of hash sets and the power of binary search to arrive at an efficient solution.

Learn more about Binary Search and Sliding Window patterns.

Solution Approach

The solution provided is a classic application of binary search with a rolling hash or a hash set to efficiently find the longest duplicated substring. Below is an explanation of the code implementation:

1. Binary Search:

   • Instead of checking all possible lengths, binary search is used to find the length of the longest duplicate substring. We initialize left as 0 and right as n - 1, where n is the length of the input string s.
   • Within a loop, we calculate mid as the average of left and right, rounded up. The >> 1 is a bitwise operation that effectively divides by 2. We are rounding up to ensure the search space reduces on each iteration.
   • We check if there is a duplicate with the length mid using a helper function. If a duplicate exists, left is set to mid. If not, right is set to mid - 1.
   • This process continues until left < right is no longer true.

2. Helper Function - check:

   • This function takes a length l and checks if any substring of this length occurs more than once.
   • We use of a set to store substrings hashes, which helps in constant-time lookups to check for duplicates.
   • The function iterates over all possible substrings of length l, creating a substring t by slicing the input string s from index i to index i + l.
   • If t is already in the vis, we have found our duplicate and return it immediately. Otherwise, we add t to vis and continue checking the next substrings.
   • If no duplicate is found, an empty string is returned.

3. Maintaining the Longest Duplicate Substring:

   • We maintain the variable ans to store the longest duplicate substring found so far.
   • After each successful check, we update ans if the length of the found duplicate t is greater than the length of ans.

4. Efficiency:

   • By using binary search, we reduce the potential search space from n(n-1)/2 to log(n), which is a significant improvement, particularly for larger strings.
   • The use of a set to store hashes implies an O(1) search time for duplicates. However, the creation of substrings and their hashes, done once per substring per iteration, has its own cost.

5. Termination and Result:

   • The loop terminates when the binary search space collapses, meaning left is equal to right, which also implies we have either found the longest duplicate substring or determined that no duplicate exists.
   • The final result is returned as ans, which is the longest duplicate found during the binary search process.

This approach is efficient for large strings because it avoids inspecting every possible substring directly. Instead, it quickly narrows down the range of possible lengths and checks for duplicates using a HashSet, considerably reducing the time complexity.

Example Walkthrough

Let's take a small example to illustrate the solution approach. Consider the string "axaxa":

1. Initial Setup:

   • We initialize left to 0 and right to 4 (since the length of "axaxa" is 5, and the max length of a duplicate substring can be n - 1).

2. First Iteration of Binary Search:

   • Calculate mid as (0 + 4) / 2, which is 2.
   • Check for duplicates of length mid (2). Here, we find that "ax" is a substring starting at index 0, and it also appears starting at index 2.

3. Update Binary Search Bounds:

   • Since we found a duplicate, we update left to mid, making it 2. We keep right at 4.

4. Second Iteration of Binary Search:

   • Calculate the new mid as (2 + 4) / 2, which is 3.
   • Check for duplicates of length 3. We see "axa" starting at index 0 and again at index 2, so a duplicate is found.

5. Keep Updating Bounds:

   • We update left to the new mid, making left now 3. Right remains 4.

6. Third Iteration of Binary Search:

   • Calculate mid as (3 + 4) / 2, which gets rounded down to 3 (since we need integers for substrings lengths).
   • Since mid is still 3 and we've already found a duplicate for length 3, the bounds don't need to be changed.

7. No Further Progress:

   • As left and right are no longer converging, the loop will terminate.

8. Termination and Result:

   • In this case, the binary search would stop here as it cannot progress further and we have found that the longest duplicated substring is "axa".

By employing binary search, we quickly identify the longest duplicate without checking every length. We start from the midpoint and either increase or decrease depending on the search results. Thus, the longest duplicated substring in "axaxa" is "axa".

Solution Implementation

Time and Space Complexity

Time Complexity

The provided code uses a binary search combined with a rolling hash (or in this case, a direct string check) for finding the longest duplicated substring in a given string. The main while loop (which is effectively the binary search) will run for O(log n) iterations, where n is the length of the input string s.

Inside the binary search, there's a call to the check function which runs for each possible substring length determined by mid. The check function iterates for each possible starting position of a substring (n - l + 1 times, with l being the length of the current substring we're checking). For each iteration, it checks if that substring has already been seen (O(1) operation for a hash set lookup on average), and if not, it adds the substring to the set (O(l) operation for hashing the substring). Therefore, the time complexity of each check call is O((n - l + 1) * l).

Since the outer loop runs O(log n) times and the check function is O((n - l + 1) * l) for each iteration, and l ranges from 0 to n, the overall time complexity is O(n log n * l), which can also be simplified to O(n^2 log n) as the worst-case scenario when l is close to n.

Space Complexity

The space complexity is dominated by the vis set, which at most will store n substrings of length l. Since Python strings are immutable and slicing a string creates a new string, the space required to store each individual substring is O(l), where l can be at most n.

Hence, in the worst case, the space complexity is O(n^2), occurring when l is close to n and we store all possible substrings of that length.

Learn more about how to find time and space complexity quickly using problem constraints.