Abstract / Summary

Find all 10 letter sequences that appear more than once in a given DNA 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 54% (1+ million submissions).

Typical patterns to solve this problem:

• Bit Manipulation
• Hash Function
• Hash Table
• Rolling Hash
• Sliding Window
• String

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 solves the classic problem of locating all 10-character substrings that appear more than once in a DNA string. It does so by converting each nucleotide into a two-bit representation, building a compact integer hash for every 10-character window, and counting occurrences with an unordered map. When a hash reaches a count of two, the corresponding substring is added to the output vector.

Core Data Structures

The class maintains a fixed-size array hashCode[256] that maps the ASCII values of the four nucleotides to small integers (0-3). This array enables O(1) translation from character to numeric code.

An unordered_map<int, short> named freq stores the frequency of each 10-character hash. The key is the integer hash, and the value is a short integer that counts how many times the hash has been seen.

The result container is a vector<string> that accumulates the repeated sequences in the order they are first discovered.

Hash Encoding

The method hashDNA receives the original string, a starting index, and a length (always 10 in this context). It iterates over the specified window, left-shifting the accumulated result by two bits for each character and adding the two-bit code from hashCode. The shift-and-add pattern builds a 20-bit integer that uniquely represents the 10-character sequence because each character contributes exactly two bits.

int hashDNA(const string& s, int from, int length)
{
    int result = 0;
    for (int i = 0; i < length; i++)
    {
        auto current = s[from + i];
        result <<= 2;
        result  += hashCode[current];
    }
    return result;
}

Sliding Window Computation

The main loop iterates with the variable last ranging from limit (10) up to the length of the input string inclusive. For each iteration, the window [last-limit, last) represents the current 10-character substring. The hash for this window is computed by calling hashDNA. Because the loop advances one character at a time, every possible 10-character substring is examined exactly once.

for (int last = limit; last <= s.size(); last++)
    if (++freq[hashDNA(s, last - limit, limit)] == 2)
        result.push_back(s.substr(last - limit, limit));

Frequency Tracking

The expression ++freq[hashDNA(...)] increments the count associated with the current hash. The conditional == 2 ensures that a substring is added to the result vector only when its count transitions from one to two. This prevents duplicate entries for substrings that appear more than twice, while still capturing every distinct repeated sequence.

Result Collection

When a hash reaches a count of two, the corresponding substring is extracted with s.substr(last - limit, limit) and appended to result. Because the check occurs at the moment the second occurrence is observed, the order of insertion reflects the order of first repetition in the original string.

Edge Cases

The code gracefully handles an empty input string or a string shorter than the required window length. In such cases, the loop condition last <= s.size() never becomes true for last starting at 10, so the body is skipped and an empty vector is returned.

If the input contains characters outside the set {A, C, G, T}, the hashCode array will contain an uninitialized value for those ASCII codes. However, the problem specification guarantees only valid nucleotides, so the implementation relies on that contract and does not need additional validation.

When the same 10-character sequence appears many times, the frequency map still stores a single entry per unique hash, and the result vector receives the substring only once, thanks to the == 2 guard.

Performance Optimizations

The two-bit encoding reduces each 10-character substring to a 20-bit integer, allowing the hash to fit comfortably within a standard 32-bit int. This compact representation minimizes memory usage for the frequency map and speeds up key comparisons.

Using a fixed-size array for character-to-code translation eliminates the overhead of a map or conditional chain during hash construction. The direct indexing hashCode[current] is a constant-time operation with negligible cache impact.

The unordered map provides average-case constant-time insertion and lookup for hash frequencies, ensuring that the overall processing time scales linearly with the length of the input string.

Incrementing the frequency and checking for the transition to two in a single statement reduces the number of map accesses per iteration.

Finally, the algorithm avoids recomputing the hash from scratch for overlapping windows; however, the current implementation does recompute the hash each time. The compact integer representation still keeps the per-iteration cost low, and the overall design balances simplicity with efficient execution.

Imagine that DNA is like a long necklace made of four different colors of beads called A, C, G, and T. These beads are strung together in a very specific order. Sometimes, a long string has the same pattern of beads repeated in different places, and this code acts like a detective to find those secret patterns.

The first part of the code acts like a tiny translator. It gives each bead a secret number so the computer can understand them better. For example, A becomes zero, C becomes one, G becomes two, and T becomes three. This makes it easy for the computer to write down the patterns as a simple math problem instead of long strings of letters.

The code then walks along the necklace ten beads at a time. It cuts out a small piece of the string and uses the secret numbers from the translator to turn that specific pattern into a single number. Think of this like giving each unique pattern its own special name tag.

As the code moves along, it keeps a list of every pattern it has seen so far. It stares at each pattern and asks if it has seen it before. If it finds a pattern that shows up for the second time, it puts that piece of the necklace into a collection bag. By the time it reaches the end of the necklace, the bag is full of all the repeated patterns, making it easy to see which ones appear more than once.

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

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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	Rust	JS	Java		Go	C#		TS
	LeetcodeHelp	C++	Python			Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python			Java
github	aylei			Rust
	black-shadows		Python
	charles-wangkai					Java
	chenyanzhe	C++
	everthis				JS
	fartem						Ruby
	gaosq0604		Python
	halfrost							Go
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	ruoru			Rust
	suxrobGM								C#
	trung-hn		Python
	varunu28					Java
	vli02									C
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
black-shadows	Python, Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
gaosq0604	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
zfang399	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