Problem Description

You are given a string s and need to find the longest substring that appears at least twice in the string. These duplicate substrings can overlap with each other.

A duplicated substring is a contiguous sequence of characters from s that occurs 2 or more times anywhere in the string. For example, in the string "banana", the substring "ana" appears twice (at positions 1-3 and 3-5), and these occurrences overlap at position 3.

Your task is to return any duplicated substring that has the maximum possible length. If no substring appears more than once in s, return an empty string "".

The solution uses binary search on the length of the potential duplicate substring. The check function verifies if there exists a duplicate substring of a given length l by iterating through all possible substrings of that length and using a set to track which substrings have been seen. If a substring is encountered that's already in the set, it means we've found a duplicate.

The binary search works by:

• Setting the search range from 0 to the length of the string
• For each middle value mid, checking if a duplicate substring of length mid exists
• If found, searching for longer duplicates (moving left pointer up)
• If not found, searching for shorter duplicates (moving right pointer down)
• Keeping track of the longest valid duplicate found so far in ans

Intuition

The key insight is that if a substring of length k appears twice in the string, then we know the answer is at least k characters long. However, there might be an even longer duplicate substring of length k+1, k+2, and so on. We want to find the maximum such length.

A brute force approach would check all possible substrings, but this would be inefficient. Instead, we can observe that the problem has a monotonic property: if there exists a duplicate substring of length k, then there must also exist duplicate substrings of all lengths from 1 to k-1. This is because any substring of a duplicate substring is also a duplicate substring.

This monotonic property suggests using binary search on the answer. We can search for the maximum length L such that there exists a duplicate substring of length L.

For each candidate length during binary search, we need to verify if any substring of that length appears twice. We can do this efficiently by:

1. Generating all substrings of the given length
2. Using a hash set to track which substrings we've seen
3. If we encounter a substring that's already in the set, we've found a duplicate

The binary search narrows down the search space from O(n) possible lengths to O(log n) checks. For each check, we examine O(n) substrings, and comparing strings takes O(L) time where L is the current length being checked. This gives us a more efficient solution than checking all possible substring pairs.

The approach elegantly combines the efficiency of binary search with the simplicity of hash-based duplicate detection, making it practical even for longer strings.

Learn more about Binary Search and Sliding Window patterns.

Solution Approach

The solution implements a binary search combined with a hash set-based duplicate detection function.

Binary Search Setup:

• Initialize left = 0 and right = n (length of string) as the search boundaries for possible substring lengths
• Use ans to keep track of the longest duplicate substring found so far

Binary Search Logic: The main loop continues while left < right:

1. Calculate mid = (left + right + 1) >> 1 (equivalent to (left + right + 1) // 2)
   • The +1 ensures we round up to avoid infinite loops when left and right are adjacent
2. Call check(mid) to verify if a duplicate substring of length mid exists
3. Update the answer: ans = t or ans keeps the non-empty result (either the new found substring t or the previous ans)
4. Adjust search boundaries:
   • If a duplicate of length mid is found, search for longer substrings: left = mid
   • Otherwise, search for shorter substrings: right = mid - 1

The check Function: This helper function determines if any substring of length l appears at least twice:

1. Initialize an empty set vis to track seen substrings
2. Iterate through all possible starting positions from 0 to n - l
3. For each position i, extract substring t = s[i : i + l]
4. If t is already in vis, we found a duplicate - return it immediately
5. Otherwise, add t to vis and continue
6. If no duplicate is found after checking all positions, return empty string

Time Complexity Analysis:

• Binary search performs O(log n) iterations
• Each check call examines O(n) substrings
• String slicing and hashing takes O(L) time for length L
• Overall: O(n * L * log n) where L is the average substring length checked

The algorithm efficiently narrows down the search space using binary search while maintaining simplicity through straightforward string comparison using Python's built-in set operations.

Example Walkthrough

Let's trace through the algorithm with the string s = "banana".

Initial Setup:

• String: "banana" (length n = 6)
• Binary search range: left = 0, right = 6
• Answer: ans = ""

Iteration 1:

• mid = (0 + 6 + 1) >> 1 = 3
• Check if any substring of length 3 appears twice:
  • i=0: "ban" → add to vis = {"ban"}
  • i=1: "ana" → add to vis = {"ban", "ana"}
  • i=2: "nan" → add to vis = {"ban", "ana", "nan"}
  • i=3: "ana" → already in vis! Return "ana"
• Found duplicate "ana", so ans = "ana"
• Search for longer: left = 3, right = 6

Iteration 2:

• mid = (3 + 6 + 1) >> 1 = 5
• Check if any substring of length 5 appears twice:
  • i=0: "banan" → add to vis = {"banan"}
  • i=1: "anana" → add to vis = {"banan", "anana"}
• No duplicates found, return ""
• No duplicate found, search for shorter: left = 3, right = 4

Iteration 3:

• mid = (3 + 4 + 1) >> 1 = 4
• Check if any substring of length 4 appears twice:
  • i=0: "bana" → add to vis = {"bana"}
  • i=1: "anan" → add to vis = {"bana", "anan"}
  • i=2: "nana" → add to vis = {"bana", "anan", "nana"}
• No duplicates found, return ""
• No duplicate found, search for shorter: left = 3, right = 3

Termination:

• left = right = 3, loop ends
• Return ans = "ana"

The algorithm correctly identifies "ana" as the longest duplicated substring. It appears at positions [1:4] and [3:6], with an overlap at position 3. Through binary search, we efficiently narrowed down from checking all possible lengths to finding the optimal length in just 3 iterations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² * log n)

The algorithm uses binary search to find the longest duplicate substring. The binary search runs for O(log n) iterations where n is the length of the string. In each iteration, the check function is called.

The check function iterates through all possible substrings of length l, which takes O(n - l + 1) ≈ O(n) iterations. For each substring, it performs:

• String slicing s[i : i + l] which takes O(l) time
• Set membership check and insertion which takes O(l) time on average (due to string hashing)

Therefore, the check function has time complexity O(n * l). In the worst case, l can be up to n/2 (when the longest duplicate substring is half the string length), making each check call O(n²) in the worst case.

Overall time complexity: O(log n) * O(n²) = O(n² * log n)

Space Complexity: O(n²)

The space complexity is dominated by the vis set in the check function. In the worst case:

• The set can store up to O(n) different substrings
• Each substring can have length up to O(n)
• Therefore, the total space used can be O(n²)

Additionally, the ans variable stores a string of length up to O(n), but this doesn't change the overall space complexity.

Overall space complexity: O(n²)

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

Common Pitfalls

1. Memory Limit Exceeded with Large Strings

The current solution stores full substring strings in a set, which can consume excessive memory when dealing with very long strings (e.g., 100,000 characters). Each substring of length L requires O(L) space, and with potentially O(n) substrings stored, memory usage can explode.

Solution: Use rolling hash (Rabin-Karp algorithm) instead of storing actual substrings:

def has_duplicate_of_length_optimized(length: int) -> str:
    if length == 0:
        return ''
  
    # Use rolling hash instead of storing strings
    base = 26
    mod = 2**63 - 1
  
    # Calculate initial hash for first substring
    hash_val = 0
    base_power = 1
    for i in range(length):
        hash_val = (hash_val * base + ord(s[i])) % mod
        if i < length - 1:
            base_power = (base_power * base) % mod
  
    seen_hashes = {hash_val}
  
    # Roll the hash through the string
    for i in range(length, len(s)):
        # Remove leftmost character and add rightmost character
        hash_val = (hash_val - ord(s[i - length]) * base_power) % mod
        hash_val = (hash_val * base + ord(s[i])) % mod
      
        if hash_val in seen_hashes:
            # Found potential duplicate, verify to avoid hash collision
            return s[i - length + 1 : i + 1]
        seen_hashes.add(hash_val)
  
    return ''

2. Incorrect Binary Search Boundaries

A common mistake is using mid = (left + right) // 2 without the +1, which can cause infinite loops when left = right - 1. If a duplicate of length mid exists, setting left = mid would keep the search stuck.

Solution: Always use mid = (left + right + 1) // 2 when updating left = mid in the success case, or alternatively use mid = (left + right) // 2 with left = mid + 1.

3. Off-by-One Error in Substring Extraction

Incorrectly calculating the range for substring extraction, such as using range(n - length) instead of range(n - length + 1), would miss the last valid substring.

Solution: Ensure the loop iterates through range(n - length + 1) to include all valid starting positions:

for start_idx in range(string_length - length + 1):  # Correct
    # Not: range(string_length - length)  # Would miss last substring

4. Hash Collision Issues (When Using Rolling Hash)

If implementing rolling hash optimization, hash collisions can lead to false positives where different substrings produce the same hash value.

Solution: When a hash match is found, perform a secondary verification or use multiple hash functions:

if hash_val in seen_hashes:
    # Verify the actual substring match
    candidate = s[i - length + 1 : i + 1]
    # Additional verification logic here
    for start_pos in seen_positions[hash_val]:
        if s[start_pos : start_pos + length] == candidate:
            return candidate

5. Performance Degradation with Short Repeated Characters

For strings with many repeated characters (e.g., "aaaaaaa..."), the check function becomes inefficient as almost every substring of a given length might need to be compared.

Solution: Add early termination conditions or use more sophisticated string matching algorithms like suffix arrays or suffix trees for better worst-case performance.