Abstract / Summary

Find the longest substring that appears at least twice in a given string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 31% (200k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method longestDupSubstring that attempts to locate the longest substring occurring at least twice within the input string s. The algorithm proceeds by iteratively testing substrings of increasing length, using Python’s built-in hash function to group identical substrings via a dictionary. An adaptive step size controls the growth of the candidate length, allowing the method to backtrack when a length yields no duplicate.

Core Algorithm

The method begins by initializing an empty result string and determining the length of the input. It then checks a simple degenerate case where the entire string consists of a repeated single character. If that condition holds, the method returns the string without its first character, which is guaranteed to be a duplicate substring.

result = ""
size = len(s)
if s[:-1] == s[1:]:
    return s[1:]

The main search loop maintains two variables: length, the current candidate substring length, and step, an increment that adapts during execution. The outer loop continues while length remains less than the size of the string.

length = 1
step   = 128
while step >= size:
    step //= 2

Inside the loop, a dictionary have maps hash values to lists of starting indices where substrings of the current length appear. For each possible start position j, the code extracts the slice s[j : j + length], computes its hash, and records the index.

have = defaultdict(list)
for j in range(size - length + 1):
    h = hash(s[j : j + length])
    have[h].append(j)

After populating the dictionary, the method scans the keys to find any hash entry associated with at least two positions. Upon locating such a key, it extracts the first occurrence as the current best result and marks that a duplicate was found.

found = False
for h in have:
    if len(have[h]) >= 2:
        found  = True
        pos    = have[h][0]
        result = s[pos : pos + length]
        break

If no duplicate exists for the current length, the algorithm reduces the length by the current step value, then halves step to prepare for a finer search. Conversely, when a duplicate is found, the length is increased by step to explore longer substrings.

if not found:
    if step == 1:
        break
    length -= step
    step  //= 2

Before increasing the length, the code ensures that the next candidate does not exceed the string bounds. It repeatedly halves step while the sum length + step would be out of range.

while step > 1 and length + step >= size:
    step //= 2
length += step

Finally, after the loop terminates, the method returns the longest duplicate substring discovered.

return result

Handling of Degenerate Input

The early check if s[:-1] == s[1:]: captures the scenario where every character in the string is identical. In such a case, any substring of length size-1 repeats, and the method promptly returns that substring without entering the more expensive search loops. This guard avoids unnecessary computation for the simplest repetitive inputs.

Hash Storage Strategy

By using Python’s native hash function on each substring slice, the implementation relies on the hash value as a proxy for equality. The dictionary have stores lists of start indices for each hash, allowing the later detection of multiple occurrences. The comment in the code explicitly acknowledges the assumption that hash collisions do not occur, which simplifies the logic to a single dictionary lookup per substring.

Adaptive Step Size Logic

The variable step starts at a power-of-two value (128) and is halved whenever the current length fails to produce a duplicate. This adaptive mechanism mimics a binary search over possible substring lengths: it quickly jumps to larger lengths, then refines the search granularity when overshooting. The initial reduction loop while step >= size: step //= 2 guarantees that step begins smaller than the string length, preventing an immediate out-of-range increment.

When a duplicate is found, the algorithm does not shrink step; instead, it proceeds to test longer substrings by adding step to length. This forward movement continues until a length fails, at which point the step size is reduced, enabling the method to converge on the maximal length that still yields a duplicate.

Loop Control and Boundary Management

Two safeguards prevent the algorithm from accessing indices beyond the string’s end. The first guard, while step > 1 and length + step >= size: step //= 2, ensures that the next increment will keep length within valid bounds. The second guard, if step == 1: break, terminates the search when the step size cannot be reduced further, indicating that the algorithm has exhausted finer granularity without finding a longer duplicate.

Edge Cases Addressed

The code explicitly handles the single-character repetition case, as described earlier. Additionally, the while-loop condition while length < size: prevents attempts to examine substrings equal to the full string length, which could never have a duplicate. The inner for loop’s range size - length + 1 correctly limits the start positions to those that produce a full slice of the desired length, avoiding index errors.

When the input string contains no repeated substrings at all, the dictionary have will never contain a key with more than one index. In that situation, found remains False, the length is reduced, and eventually the step size reaches 1, causing the loop to break and return the initially empty result. Thus the method gracefully returns an empty string for inputs lacking any duplicate substrings.

Performance Optimizations

The adaptive step size reduces the number of length values examined compared to a naïve linear scan. By halving step only when necessary, the algorithm avoids redundant checks for lengths that are unlikely to succeed. The early termination for the all-identical character case eliminates the need for hashing the entire string when the answer is obvious.

Using a dictionary keyed by hash values provides O(1) average-time insertion and lookup for each substring slice, allowing the method to group identical substrings efficiently. The storage of only start indices (rather than the substrings themselves) minimizes memory overhead, especially for large inputs where many overlapping substrings would otherwise be duplicated in memory.

The inner loop iterates over size - length + 1 positions, and the outer loop’s step adjustments ensure that the total number of iterations stays bounded by a logarithmic factor relative to the string length. This combination of hash-based grouping and binary-search-style length progression yields a practical runtime for typical input sizes.

Imagine playing with a long necklace made of colorful letter beads. This code helps find the longest pattern of beads that appears two or more times in the string. It starts by picking a small length of beads and looks at every group of that size to see if any of them are exactly the same as others. To do this quickly, it turns each group of letters into a secret number code so it can check them faster.

If it finds a matching pair, it remembers that pattern and then tries to see if it can find an even longer pattern by adding more beads to compare. If it does not find any matching pairs, it tries a slightly different length to keep searching. The code keeps adjusting how many letters it checks at once, moving through the necklace space until it discovers the biggest repeating piece possible. It is like being a detective searching for the biggest shared secret hidden inside a long line of letters.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java		TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python			Java	Go
	LeetcodeHelp	C++	Python			Java
	Progiez	C++	Python			Java
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai					Java
	everthis			JS
	fpdjsns	C++
	fsq	C++
	Garvit244		Python
	halfrost						Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM				C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality