Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

DNA Short Tandem Repeats

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

Bạn sẽ học được gì

  • 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

Đề bài

Xem bản dịch

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.

Ràng buộc

0 ≤ length of sequence ≤ 5,000

1 ≤ number of units ≤ 10

Each unit has 1 to 8 letters

Ví dụ

Ví dụ 1
Đầu vào:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]

Kết quả mong đợi:
expected = [3, 1]
Đầu vào:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};

Kết quả mong đợi:
std::vector<long long> expected = {3, 1};
Đầu vào:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};

Kết quả mong đợi:
long[] expected = new long[] {3, 1};

Giải thích

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

Ví dụ 2
Đầu vào:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]

Kết quả mong đợi:
expected = [3, 1, 0]
Đầu vào:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};

Kết quả mong đợi:
std::vector<long long> expected = {3, 1, 0};
Đầu vào:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};

Kết quả mong đợi:
long[] expected = new long[] {3, 1, 0};

Giải thích

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

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

Try every start position and remember the largest run.

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.