โจทย์
ห้องแล็บนิติวิทยาศาสตร์เปรียบเทียบบุคคลด้วยลำดับซ้ำต่อเนื่องสั้น (short tandem repeats หรือ STR) ซึ่งเป็นหน่วย DNA สั้น ๆ เช่น AGAT ที่ปรากฏซ้ำติดกันหลายครั้ง สำหรับแต่ละหน่วย ห้องแล็บจะบันทึกจำนวนครั้งที่ซ้ำติดกันยาวที่สุดในลำดับ ใน TTAGATAGATAGATCAGATAGAT หน่วย AGAT ปรากฏติดกันสามครั้งช่วงต้น และสองครั้งในภายหลัง จำนวนของมันจึงเป็น 3
จงเขียน dna_str_count(sequence, repeats)
อินพุต
sequence: ลำดับ DNA ที่ประกอบด้วยตัวอักษร A, C, G และ T
repeats: หน่วย STR ที่ต้องการวัด
เอาต์พุต
คืนค่าจำนวนหนึ่งค่าต่อหนึ่งหน่วย เรียงตามลำดับเดียวกับ repeats โดยเป็นจำนวนครั้งมากที่สุดที่หน่วยนั้นปรากฏติดกัน หน่วยที่ไม่ปรากฏเลยมีค่าเป็น 0
เงื่อนไข
0 ≤ ความยาวของ sequence ≤ 5,000
1 ≤ จำนวนหน่วย ≤ 10
แต่ละหน่วยมีตัวอักษร 1 ถึง 8 ตัว
ตัวอย่าง
อินพุต:
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 ซ้ำติดกัน 3 ครั้งที่ต้นลำดับ และเพียง 2 ครั้งที่ท้าย จึงได้ 3 ส่วน CA ปรากฏครั้งเดียว จึงได้ 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 ซ้ำ 3 ครั้ง TATC ปรากฏครั้งเดียว และ GATA ไม่ปรากฏเลย ได้ [3, 1, 0]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
จากตำแหน่งเริ่มต้น ให้กระโดดไปข้างหน้าทีละความยาวของหน่วย ตราบใดที่ชิ้นถัดไปยังเหมือนกับหน่วยนั้น
คำใบ้ 2
ลองทุกตำแหน่งเริ่มต้น แล้วจำช่วงที่ยาวที่สุดไว้
คำใบ้ 3
หน่วยที่ไม่เคยตรงเลยจะทำให้จำนวนที่ดีที่สุดยังเป็น 0
ความซับซ้อนที่คาดหวัง
เวลา O(n × m × k), หน่วยความจำเพิ่ม O(m)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน