Show problems as
Classic problem #1044HardStringBinary SearchSliding WindowRolling HashSuffix ArrayHash FunctionSuffix AutomatonSuffix TreeZ AlgorithmBoyer–Moore String-Search Algorithm

Longest Duplicate Substring

Real-world version: Longest Repeated Stretch on a Log Line
Tracked in this browser only
Read Longest Duplicate Substring on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_dup_substring(s: str) -> str:
Java
public String longestDupSubstring(String s)

More on the same topics