Recurring Gene Windows

Medium

A DNA strand is written as a string strand of the letters A, C, G and T. Find every segment of length exactly 10 (a substring of 10 consecutive letters) that occurs in strand more than once. Occurrences may overlap. List each such segment once; the order of the segments in the answer does not matter.

Example 1

strand="GATTACAGATTACAGAT" → ['GATTACAGAT']

The fragment GATTACAGAT starts at positions 0 and 7. Every other window of length 10 occurs only once.

Example 2

strand="CCCCCCCCCCCC" → ['CCCCCCCCCC']

The window CCCCCCCCCC occurs three times (windows may overlap), but it is listed only once.

Example 3

strand="ACGT" → []

The strand is shorter than 10 letters, so there are no windows and the answer is empty.

Constraints

1 ≤ len(strand) ≤ 10⁵
Every character of strand is one of A, C, G, T

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Hash Table String Sliding Window Hash Function Rolling Hash

Similar problems

Every Bit Pattern Inside Medium Two Words One Letter Apart Medium Evenly Mixed Digit Pieces Medium Longest Repeated Fragment Hard Both Cases Stretch Easy

Input

strand="GATTACAGATTACAGAT"

Expected

['GATTACAGAT']

Run checks the first 3 tests in your browser. Submit checks all 140 tests on the server, hidden ones included.