0599HardStringBinary SearchSliding WindowRolling HashSuffix ArrayHash FunctionSuffix AutomatonSuffix TreeZ AlgorithmBoyer–Moore String-Search Algorithm

Longest Repeated Stretch on a Log Line

Tracked in this browser only

Write code

Trains the technique from

LeetCode 1044Longest Duplicate Substring

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A device writes one long line of lowercase letters into its log, given to you as s. A stretch is any block of one or more letters that sit next to each other on that line.

A stretch is called echoed when it can be read off starting at two different positions of s. The two readings are permitted to overlap, so the line aaa has the echoed stretch aa.

Return the longest echoed stretch of s. Should several echoed stretches tie for the greatest length, return the one whose first appearance in s starts furthest to the left. If s has no echoed stretch, return the empty string "".

Examples

Example 1

Input: s = "abcabd"
Output: "ab"

The stretch `ab` can be read at position 0 and again at position 3, so it is echoed. No echoed stretch of `s` is longer than two letters.

Example 2

Input: s = "xyzwxyzwabcdabcd"
Output: "xyzw"

Both `xyzw` and `abcd` are echoed and both are four letters long. The first appearance of `xyzw` starts at position 0 while the first appearance of `abcd` starts at position 8, so `xyzw` wins the tie.

Example 3

Input: s = "aaaa"
Output: "aaa"

`aaa` can be read at position 0 and again at position 1; those two readings overlap, which the rules allow.

Constraints

2 <= s.length <= 3 * 10^4
s consists of lowercase English letters.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_dup_substring(s: str) -> str:

Java

public String longestDupSubstring(String s)

The intended approach

Time O(n log n) on average: log n width probes, each a linear rolling-hash sweep, with letter comparisons only on a hash clash.Space O(n) for the table of window hashes and the returned stretch.

Whenever a stretch of some width is echoed, so is the stretch obtained by dropping its last letter, so the set of workable widths is a prefix of `1, 2, 3, ...` and can be bisected. For one fixed width, hash every window of that width with a rolling hash so each window costs constant work, keep the starts grouped by hash value, and whenever a later window meets a hash already recorded compare the two windows letter by letter to rule out an accidental clash. The smallest confirmed earlier start is what the width probe reports, and the last width the bisection accepts supplies the answer.

Pythonentry point: longest_dup_substring

def longest_dup_substring(s):
    # O(n log n) rolling-hash passes on average, plus a direct comparison
    # whenever two windows hash alike, which is what keeps the answer exact.
    # O(n) space for the table of window hashes.
    n = len(s)
    codes = [ord(ch) - 97 for ch in s]
    mod = (1 << 61) - 1
    base = 131

    def earliest_repeat(width):
        """Smallest start whose window of this width shows up again later, else -1."""
        power = pow(base, width, mod)
        rolling = 0
        for i in range(width):
            rolling = (rolling * base + codes[i]) % mod
        table = {rolling: [0]}
        found = -1
        for start in range(1, n - width + 1):
            rolling = (rolling * base
                       - codes[start - 1] * power
                       + codes[start + width - 1]) % mod
            bucket = table.get(rolling)
            if bucket is None:
                table[rolling] = [start]
                continue
            window = s[start:start + width]
            for older in bucket:
                if s[older:older + width] == window:
                    if found == -1 or older < found:
                        found = older
                    break
            bucket.append(start)
        return found

    # A repeated stretch of width w contains a repeated stretch of width w - 1,
    # so the widths that work form a prefix of 1, 2, ... and can be bisected.
    low = 1
    high = n - 1
    answer = ""
    while low <= high:
        mid = (low + high) // 2
        spot = earliest_repeat(mid)
        if spot >= 0:
            answer = s[spot:spot + mid]
            low = mid + 1
        else:
            high = mid - 1
    return answer

The obvious version

Try widths from the largest downward, and for each width walk the starts from left to right, cutting out the window and searching for it in the part of the line that begins one position later. The first hit found is returned.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_longest_dup_substring(s):
    n = len(s)
    for width in range(n - 1, 0, -1):
        for start in range(n - width + 1):
            piece = s[start:start + width]
            if piece in s[start + 1:]:
                return piece
    return ""

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in