What is the time complexity of Longest Duplicate Substring?

The optimal solution has a time complexity of O(NlogN).

What data structures are used to solve Longest Duplicate Substring?

This problem uses String, Binary Search, Sliding Window, Rolling Hash, Suffix Array, Hash Function. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Longest Duplicate Substring?

Insight 1: Binary search can be used to efficiently search for the length of the longest duplicate substring. We can check if a duplicate substring of a certain length exists in O(n) time. Insight 2: Rolling hash can efficiently compute the hash values of all substrings of a given length. By maintaining a hash table of seen hash values, we can quickly identify potential duplicate substrings.

Which companies ask LeetCode 1044. Longest Duplicate Substring in interviews?

This problem is frequently asked at Coupang.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Longest Duplicate Substring - LeetCode 1044 Solution

Q: How to solve Longest Duplicate Substring?

The solution uses a binary search approach to find the length of the longest duplicate substring. For a given length `L`, it uses a rolling hash function to compute the hash values of all substrings of length `L` in O(n) time. It stores these hash values in a hash map (or unordered map), along with the starting indices of the corresponding substrings. During the rolling hash process, if a hash value is already present in the hash map, it checks for actual string equality to confirm the substring duplication and returns the index. The binary search continues until the maximum possible length of the duplicate substring is found.

Longest Duplicate Substring - Complete Solution Guide

Longest Duplicate Substring is LeetCode problem 1044, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 * 10 4 s consists of lowercase English letters.

Detailed Explanation

The problem asks us to find the longest substring that appears at least twice within a given string `s`. The occurrences of the substring can overlap. If no such substring exists, return an empty string.

Solution Approach

The solution uses a binary search approach to find the length of the longest duplicate substring. For a given length `L`, it uses a rolling hash function to compute the hash values of all substrings of length `L` in O(n) time. It stores these hash values in a hash map (or unordered map), along with the starting indices of the corresponding substrings. During the rolling hash process, if a hash value is already present in the hash map, it checks for actual string equality to confirm the substring duplication and returns the index. The binary search continues until the maximum possible length of the duplicate substring is found.

Step-by-Step Algorithm

Step 1: Initialize `low` to 1 and `high` to `n - 1`, where `n` is the length of the input string `s`. These represent the minimum and maximum possible lengths of a duplicate substring.
Step 2: Perform binary search while `low <= high`. In each iteration, calculate the middle value `mid = low + (high - low) // 2`. This `mid` value represents the length of the substring we are currently searching for.
Step 3: Implement a `search(mid)` function that checks if a duplicate substring of length `mid` exists. This function uses a rolling hash approach.
Step 4: Inside `search(mid)`, compute the hash value of the first substring of length `mid`. Store this hash value and its starting index in a hash map.
Step 5: Iterate through the remaining substrings of length `mid`, updating the hash value using the rolling hash technique. This efficiently calculates the hash value of the next substring based on the previous one.
Step 6: If a hash value is already present in the hash map, perform an explicit string comparison to confirm the duplicate substring due to potential hash collisions.
Step 7: If a duplicate substring of length `mid` is found, update `ans_len` to `mid` and `ans_start` to the starting index of the duplicate. Then, set `low = mid + 1` to search for a longer duplicate substring.
Step 8: If no duplicate substring of length `mid` is found, set `high = mid - 1` to search for a shorter duplicate substring.
Step 9: After the binary search completes, return the duplicate substring of length `ans_len` starting at index `ans_start`.

Key Insights

Insight 1: Binary search can be used to efficiently search for the length of the longest duplicate substring. We can check if a duplicate substring of a certain length exists in O(n) time.
Insight 2: Rolling hash can efficiently compute the hash values of all substrings of a given length. By maintaining a hash table of seen hash values, we can quickly identify potential duplicate substrings.
Insight 3: A crucial optimization is using a large prime number (ideally 2^64) as the modulus in the rolling hash to minimize the chance of hash collisions. Explicit collision checking is necessary when collisions occur.

Complexity Analysis

Time Complexity: O(NlogN)

Space Complexity: O(N)

Topics

This problem involves: String, Binary Search, Sliding Window, Rolling Hash, Suffix Array, Hash Function.

Companies

Asked at: Coupang.

Longest Duplicate Substring | LeetCode 1044

Hard

String Binary Search Sliding Window Rolling Hash Suffix Array Hash Function

Time: O(NlogN)Space: O(N)

Solution Code

Available in:

class Solution {
    public String longestDupSubstring(String s) {
        int n = s.length();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = s.charAt(i) - 'a';
        }
        int base = 26;
        long modulus = (long) Math.pow(2, 64);

        class Pair {
            long hash;
            int index;

            public Pair(long hash, int index) {
                this.hash = hash;
                this.index = index;
            }
        }

        class SearchResult {
            int index;

            public SearchResult(int index) {
                this.index = index;
            }
        }

        SearchResult search(int L) {
            if (L == 0) {
                return new SearchResult(0);
            }
            if (L > n) {
                return new SearchResult(-1);
            }

            long h_factor = 1;
            for(int i = 0; i < L; i++){
                h_factor = (h_factor * base) % modulus;
            }
           
            long current_h = 0;
            for (int i = 0; i < L; i++) {
                current_h = (current_h * base + nums[i]) % modulus;
            }

            java.util.Map<Long, java.util.List<Integer>> seen = new java.util.HashMap<>();
            java.util.List<Integer> initialList = new java.util.ArrayList<>();
            initialList.add(0);
            seen.put(current_h, initialList);

            for (int i = 1; i < n - L + 1; i++) {
                current_h = (current_h * base - (long) nums[i - 1] * h_factor % modulus + modulus) % modulus;
                current_h = (current_h + nums[i + L - 1]) % modulus;

                if (seen.containsKey(current_h)) {
                    for (int start_idx : seen.get(current_h)) {
                        if (s.substring(start_idx, start_idx + L).equals(s.substring(i, i + L))) {
                            return new SearchResult(i);
                        }
                    }
                    seen.get(current_h).add(i);
                } else {
                    java.util.List<Integer> newList = new java.util.ArrayList<>();
                    newList.add(i);
                    seen.put(current_h, newList);
                }
            }

            return new SearchResult(-1);
        }

        int ans_start = -1;
        int ans_len = 0;
        int low = 1, high = n;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) {
                break;
            }

            SearchResult searchResult = search(mid);
            int start_idx = searchResult.index;
            if (start_idx != -1) {
                ans_len = mid;
                ans_start = start_idx;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        if (ans_start == -1) {
            return "";
        } else {
            return s.substring(ans_start, ans_start + ans_len);
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1044: Longest Duplicate Substring - Detailed explanation and solution approaches.

Topics

String Binary Search Sliding Window Rolling Hash Suffix Array Hash Function

Companies

Coupang

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:1044

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Initialize `low` to 1 and `high` to `n - 1`, where `n` is the length of the input string `s`. These represent the minimum and maximum possible lengths of a duplicate substring.
2
Step 2: Perform binary search while `low <= high`. In each iteration, calculate the middle value `mid = low + (high - low) // 2`. This `mid` value represents the length of the substring we are currently searching for.
3
Step 3: Implement a `search(mid)` function that checks if a duplicate substring of length `mid` exists. This function uses a rolling hash approach.
4
Step 4: Inside `search(mid)`, compute the hash value of the first substring of length `mid`. Store this hash value and its starting index in a hash map.
5
Step 5: Iterate through the remaining substrings of length `mid`, updating the hash value using the rolling hash technique. This efficiently calculates the hash value of the next substring based on the previous one.
6
Step 6: If a hash value is already present in the hash map, perform an explicit string comparison to confirm the duplicate substring due to potential hash collisions.
7
Step 7: If a duplicate substring of length `mid` is found, update `ans_len` to `mid` and `ans_start` to the starting index of the duplicate. Then, set `low = mid + 1` to search for a longer duplicate substring.
8
Step 8: If no duplicate substring of length `mid` is found, set `high = mid - 1` to search for a shorter duplicate substring.
9
Step 9: After the binary search completes, return the duplicate substring of length `ans_len` starting at index `ans_start`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(NlogN)

💾

Space Complexity

O(N)

📝

Why?

The binary search takes O(logN) time. For each value of `mid` in the binary search, the `search` function takes O(N) time due to the rolling hash and substring comparison in case of hash collision. Therefore, the overall time complexity is O(NlogN). The hash map used in the `search` function can store up to O(N) hash values in worst-case (when all substrings have different hash values), making space complexity O(N).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Suffix Array

Construct a suffix array for the given string. Find the longest common prefix (LCP) between adjacent suffixes in the sorted suffix array. The longest LCP corresponds to the longest duplicate substring.

Time: O(NlogN) or O(N) depending on the suffix array construction algorithmSpace: O(N)

Trade-offs: Suffix arrays can be more memory-efficient in some cases, especially when dealing with very long strings. However, suffix array construction can be more complex to implement than the rolling hash approach.

✨

Key Insights

1Insight 1: Binary search can be used to efficiently search for the length of the longest duplicate substring. We can check if a duplicate substring of a certain length exists in O(n) time.
2Insight 2: Rolling hash can efficiently compute the hash values of all substrings of a given length. By maintaining a hash table of seen hash values, we can quickly identify potential duplicate substrings.
3Insight 3: A crucial optimization is using a large prime number (ideally 2^64) as the modulus in the rolling hash to minimize the chance of hash collisions. Explicit collision checking is necessary when collisions occur.

📚

Key Terms Explained

For Students

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Sliding Window

A moving "window" over data to process subsets efficiently.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Input string `s` is empty or has length 1. The solution correctly returns an empty string because `low` will be initialized to 1, `high` to string length, so that low > high. and hence will return ''.
Edge case 2: The input string `s` contains no duplicate substrings. The binary search will terminate with `ans_start` remaining -1, and the solution correctly returns an empty string.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling hash collisions properly. Failing to check for string equality when hash values match can lead to incorrect results.

✗Common mistake 2: Integer overflow in the rolling hash calculation. Using a large prime modulus (e.g., 2^64 ) and unsigned long long can help mitigate this issue. Using modulo after each operation in rolling hash.

✗Common mistake 3: Not checking for edge cases where the string is too short to have duplicate substrings.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Detecting plagiarism in text documents. The longest duplicate substring can identify similar or copied sections of text.

🏦Real-world scenario 2: Bioinformatics: Finding repeating sequences in DNA or protein sequences. These repeating sequences can have important biological functions.

🎮Real-world scenario 3: Data compression. Identifying repeating patterns can be used to improve the efficiency of data compression algorithms.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 23, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I avoid off-by-one errors in binary search?

Use the pattern: left = 0, right = n-1, while (left <= right), mid = left + (right - left) / 2. Decide if you need to find exact match, first occurrence, or last occurrence, and adjust your conditions accordingly. Test with arrays of size 0, 1, and 2.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Longest Duplicate Substring"?

For this hard-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether binary search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?