How do you solve Longest Duplicate Substring on LeetCode?

Longest Duplicate Substring (LeetCode #1044) can be solved using Brute Force. The optimal approach is Brute Force with O(n²) time complexity and O(1) space complexity. Key insight: The brute-force approach involves generating all possible substrings of the input string and checking for duplicates. This method is straightforward but inefficient for larger strings.

Longest Duplicate Substring — LeetCode #1044 (Hard)

Tags: String, Binary Search, Sliding Window, Rolling Hash, Suffix Array, Hash Function

Related patterns:

Brute Force approach

Time complexity: O(n²). Space complexity: O(1).

The brute-force approach involves generating all possible substrings of the input string and checking for duplicates. This method is straightforward but inefficient for larger strings.

The time complexity is O(n²) because we generate all substrings in a nested loop, and checking for duplicates takes linear time. The space complexity is O(1) as we are not using any additional data structures that grow with input size.

Step 1: Generate all possible substrings of the string.
Step 2: Store each substring in a set and check if it already exists in the set.
Step 3: Keep track of the longest substring found that has duplicates.

For the input 'banana': 1. i=0, j=1: substring='b' (not duplicate) 2. i=0, j=2: substring='ba' (not duplicate) 3. i=0, j=3: substring='ban' (not duplicate) 4. i=0, j=4: substring='bana' (not duplicate) 5. i=0, j=5: substring='banan' (not duplicate) 6. i=0, j=6: substring='banana' (not duplicate) 7. i=1, j=3: substring='an' (not duplicate) 8. i=1, j=4: substring='ana' (duplicate found, longest='ana')

#1044

Longest Duplicate Substring

Hard

String↗Binary Search↗Sliding Window↗Rolling Hash↗Suffix Array↗Hash Function↗

LeetCode ↗

Approaches

💡

Intuition

Time O(n²)Space O(1)

The brute-force approach involves generating all possible substrings of the input string and checking for duplicates. This method is straightforward but inefficient for larger strings.

⚙️

Algorithm

3 steps

1Step 1: Generate all possible substrings of the string.
2Step 2: Store each substring in a set and check if it already exists in the set.
3Step 3: Keep track of the longest substring found that has duplicates.

solution.py13 lines

1# Full working Python code
2
3def longest_duplicate_substring(s):
4    n = len(s)
5    longest = ""
6    for i in range(n):
7        for j in range(i + 1, n + 1):
8            substring = s[i:j]
9            if s.count(substring) > 1 and len(substring) > len(longest):
10                longest = substring
11    return longest
12
13print(longest_duplicate_substring("banana"))  # Output: "ana"

ℹ

Complexity note: The time complexity is O(n²) because we generate all substrings in a nested loop, and checking for duplicates takes linear time. The space complexity is O(1) as we are not using any additional data structures that grow with input size.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.