All challenges
Medium 0 solved 0% acceptance

DNA Short Tandem Repeats

For each short tandem repeat, find the longest run of back-to-back copies in a DNA sequence.

What you'll learn

  • Compare a substring of a string with a pattern
  • Count back-to-back copies starting at a position
  • Keep the best count for each pattern

Problem

Forensic labs compare people by short tandem repeats (STRs): short DNA units such as AGAT that appear many times in a row. For each unit, the lab records the longest run of consecutive copies anywhere in the sequence. In TTAGATAGATAGATCAGATAGAT the unit AGAT appears three times in a row near the start and twice later, so its count is 3.

Implement dna_str_count(sequence, repeats).

Input

sequence: The DNA sequence, using the letters A, C, G and T.

repeats: The STR units to measure.

Output

Return one count per unit, in the same order as repeats: the largest number of copies that appear back to back. A unit that never appears has count 0.

Constraints

0 ≤ length of sequence ≤ 5,000

1 ≤ number of units ≤ 10

Each unit has 1 to 8 letters

Examples

Example 1
Input:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]

Expected output:
expected = [3, 1]
Input:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};

Expected output:
std::vector<long long> expected = {3, 1};
Input:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};

Expected output:
long[] expected = new long[] {3, 1};

Explanation

AGAT runs 3 times at the start and only twice at the end, so it scores 3; CA appears once, so it scores 1.

Example 2
Input:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]

Expected output:
expected = [3, 1, 0]
Input:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};

Expected output:
std::vector<long long> expected = {3, 1, 0};
Input:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};

Expected output:
long[] expected = new long[] {3, 1, 0};

Explanation

AATG repeats 3 times, TATC once and GATA never: [3, 1, 0].

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

From a start position, keep jumping forward by the unit length while the next piece equals the unit.

Hint 2

Try every start position and remember the largest run.

Hint 3

A unit that never matches leaves the best count at 0.

Expected complexity

O(n × m × k) time, O(m) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.