Is Repeated DNA Sequences easy or hard?

Repeated DNA Sequences is considered a medium difficulty problem. The basic sliding window and hashing solution is straightforward, but recognizing the bit manipulation optimization with 2-bit encoding requires deeper understanding of hashing and memory-efficient representations.

Repeated DNA Sequences Python/Java solution

Python and Java implementations usually rely on a sliding window and a hash map or set to store 10-character substrings. Each iteration extracts the substring, checks if it has appeared before, and records duplicates. The logic runs in linear time and is easy to implement in high-level languages.

How to solve Repeated DNA Sequences in O(n)?

Scan the string using a fixed-size sliding window of length 10. Store each sequence in a hash set or hash map and track duplicates. A more optimized version encodes each DNA character with 2 bits and maintains a rolling 20-bit hash, allowing constant-time updates while scanning the string once.

What is the best approach for Repeated DNA Sequences?

The most practical approach uses a sliding window of length 10 with a hash map to track seen substrings. Each window substring is inserted into the hash table and duplicates are recorded when the count reaches two. This method runs in O(n) time with O(n) space and is simple to explain in interviews.

Is Repeated DNA Sequences asked at Google/Amazon/Meta?

Repeated DNA Sequences is a common medium-level string and hashing problem seen in interviews at large tech companies. Variants involving substring hashing, rolling hashes, and duplicate detection appear in interviews at companies like Amazon and Google.

What data structure is used in Repeated DNA Sequences?

Hash tables or hash sets are the primary data structures used to track previously seen sequences. In optimized solutions, bit manipulation combined with a rolling hash encodes sequences into integers while still using a hash set for duplicate detection.

What is the time complexity of Repeated DNA Sequences?

The optimal solutions run in O(n) time where n is the length of the DNA string. Each position is processed once using a sliding window, and hash lookups are constant time on average. Space complexity is O(n) due to storing seen sequences or encoded hashes.

Description Solution Video 7:31

187. Repeated DNA Sequences

Medium54.3% acceptance7 companies

The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.

For example, "ACGAATTCCG" is a DNA sequence.

When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

Example 1:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

Example 2:

Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]

Constraints:

1 <= s.length <= 10⁵
s[i] is either 'A', 'C', 'G', or 'T'.

Asked at 7 companies

Grammarly LinkedIn Bloomberg

Google Amazon Microsoft Meta

Topics

7:31

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def findRepeatedDnaSequences(self, s: str) -> List[str]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Input

"AAAAAAAAAAAAA"

Your code is saved on this device.Solution