समस्या
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.
सीमाएँ
0 ≤ length of sequence ≤ 5,000
1 ≤ number of units ≤ 10
Each unit has 1 to 8 letters
उदाहरण
इनपुट:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]
अपेक्षित आउटपुट:
expected = [3, 1]
इनपुट:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};
अपेक्षित आउटपुट:
std::vector<long long> expected = {3, 1};
इनपुट:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};
अपेक्षित आउटपुट:
long[] expected = new long[] {3, 1};
व्याख्या
AGAT runs 3 times at the start and only twice at the end, so it scores 3; CA appears once, so it scores 1.
इनपुट:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]
अपेक्षित आउटपुट:
expected = [3, 1, 0]
इनपुट:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};
अपेक्षित आउटपुट:
std::vector<long long> expected = {3, 1, 0};
इनपुट:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};
अपेक्षित आउटपुट:
long[] expected = new long[] {3, 1, 0};
व्याख्या
AATG repeats 3 times, TATC once and GATA never: [3, 1, 0].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
From a start position, keep jumping forward by the unit length while the next piece equals the unit.
संकेत 2
Try every start position and remember the largest run.
संकेत 3
A unit that never matches leaves the best count at 0.
अपेक्षित जटिलता
O(n × m × k) time, O(m) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।