How hard is LeetCode 1044. Longest Duplicate Substring?

LeetCode 1044. Longest Duplicate Substring is rated Hard on LeetCode.

What topics does LeetCode 1044. Longest Duplicate Substring cover?

LeetCode 1044. Longest Duplicate Substring is tagged String, Binary Search, Suffix Array, Sliding Window, Hash Function and Rolling Hash on LeetCode.

Longest Duplicate Substring — LeetCode 1044 Python Solution

HardStringBinary SearchSuffix ArraySliding WindowHash FunctionRolling Hash

Problem: #1044
Pattern: Sliding Window
Reading time: 4 min
Source: leetcode.com

The problem

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Example

Input: s = "banana"
Output: "ana"

Python solution

Python

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        def check(l):
            vis = set()
            for i in range(n - l + 1):
                t = s[i : i + l]
                if t in vis:
                    return t
                vis.add(t)
            return ''

        n = len(s)
        left, right = 0, n
        ans = ''
        while left < right:
            mid = (left + right + 1) >> 1
            t = check(mid)
            ans = t or ans
            if t:
                left = mid
            else:
                right = mid - 1
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(1) to O(n) auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1044. Longest Duplicate Substring is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1044. Longest Duplicate Substring?: LeetCode 1044. Longest Duplicate Substring is rated Hard on LeetCode.
What topics does LeetCode 1044. Longest Duplicate Substring cover?: LeetCode 1044. Longest Duplicate Substring is tagged String, Binary Search, Suffix Array, Sliding Window, Hash Function and Rolling Hash on LeetCode.