मध्यम 0 हल किए गए 0% स्वीकृति

DNA Short Tandem Repeats

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

आप क्या सीखेंगे

  • 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

समस्या

अनुवाद दिखाएँ

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

उदाहरण

उदाहरण 1
इनपुट:
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.

उदाहरण 2
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।