Longest Echoed Fragment
HardTries & Strings
Problem
A DNA-like log may contain fragments that occur more than once. Given s, return the length of the longest substring that occurs at least twice in s (occurrences may overlap). Return 0 if no substring repeats.
Example 1
- Input:
- s = "banana"
- Output:
- 3
"ana" occurs at positions 1 and 3, overlapping on one letter.
Example 2
- Input:
- s = "abcd"
- Output:
- 0
Example 3
- Input:
- s = "aaaa"
- Output:
- 3
"aaa" starts at 0 and at 1.
Constraints
- 1 ≤ s.length ≤ 3·10^4
- Lowercase English letters only.
Hint
Show the first hint
If some substring of length L repeats, does a substring of length L - 1 repeat too?
Walkthrough
How to approach it
01Clarify before coding
- Can the two occurrences overlap? Yes ("aaa" in "aaaa").
- Return the substring or its length? The length; 0 if nothing repeats.
- Alphabet? Lowercase letters only.
02Brute force
For each length from n - 1 down, put every substring of that length in a set and stop at the first repeat.
Cost: O(n³) in the worst case: n lengths × n substrings × O(n) to hash each slice.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.