Show problems as
Classic problem #187MediumHash TableStringBit ManipulationSliding WindowRolling HashHash FunctionZ AlgorithmBoyer–Moore String-Search Algorithm

Repeated DNA Sequences

Real-world version: Ten-Letter Runs That Come Round Again
Tracked in this browser only
Read Repeated DNA Sequences on LeetCode(opens in a new tab)

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

A strand reads s, a string over the four letters 'A', 'C', 'G' and 'T'.

Return every run of exactly ten letters that appears in the strand more than once, each run listed once, in the order they first appear.

Examples

Example 1

Input
s = "GGTCAGGTCAGGTCATTTGCA"
Output
["GGTCAGGTCA"]

The run "GGTCAGGTCA" starts at both position 0 and position 5, so it comes round again. No other ten-letter run repeats.

Example 2

Input
s = "GATTACAGATTACAGATTACA"
Output
["GATTACAGAT", "ATTACAGATT", "TTACAGATTA", "TACAGATTAC", "ACAGATTACA"]

Two runs repeat here, and they are listed in the order they first appear.

Example 3

Input
s = "ACGTACGTAC"
Output
[]

The strand is exactly ten letters long, so there is only one run and nothing can repeat.

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is 'A', 'C', 'G' or 'T'

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 find_repeated_dna_sequences(s: str) -> list[str]:
Java
public List<String> findRepeatedDnaSequences(String s)

More on the same topics