ปานกลาง 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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก