Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

DNA Short Tandem Repeats

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

Das lernst du

  • 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

Übersetzung anzeigen

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.

Einschränkungen

0 ≤ length of sequence ≤ 5,000

1 ≤ number of units ≤ 10

Each unit has 1 to 8 letters

Beispiele

Beispiel 1
Eingabe:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]

Erwartete Ausgabe:
expected = [3, 1]
Eingabe:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};

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

Erwartete Ausgabe:
long[] expected = new long[] {3, 1};

Erläuterung

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

Beispiel 2
Eingabe:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]

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

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

Erwartete Ausgabe:
long[] expected = new long[] {3, 1, 0};

Erläuterung

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

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

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

Hinweis 2

Try every start position and remember the largest run.

Hinweis 3

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

Erwartete Komplexität

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

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.