TandemRepeats
SRM 185 · 2004-03-01 · by vorthys
Problem Statement
An important problem in DNA analysis is finding tandem repeats. A tandem repeat occurs when a base sequence of nucleotides appears twice in a row. (In this problem, a base sequence is simply a contiguous substring and a nucleotide is simply a letter.) For example, in the DNA sequence "GATCATCA", the base sequence "ATC" appears twice in a row. In contrast, "ATCGATC" is not a tandem repeat of the base sequence "ATC" because of the 'G' in between the two copies.
Real DNA often contains errors in which one nucleotide is substituted for another. A k-approximate tandem repeat occurs when a base sequence of nucleotides appears twice in a row, allowing the second copy of the base sequence to differ from the first copy in at most k nucleotides. For example, in the DNA sequence "GATCATGA", the base sequence "ATC" is immediately repeated with a single error as "ATG". Thus, "ATCATG" is a 1-approximate tandem repeat. Note that both copies of the base sequence must be the same length.
Given a DNA sequence dna (represented as a
Constraints
- dna contains between 2 and 50 characters, inclusive.
- Every character in dna is a 'G', 'A', 'T', or 'C'.
- k is between 0 and 5, inclusive.
"GATCATCA" 0 Returns: 3
A tandem repeat with a base sequence of length 3 is "ATCATC", with base sequence "ATC".
"GATCATGA" 1 Returns: 3
A 1-approximate tandem repeat is "ATCATG". The base sequence "ATC" is repeated with a single error.
"GATCATGA" 0 Returns: 0
This example has no tandem repeats.
"AGAGAAAGAA" 3 Returns: 5
"ATTAGCATTGCACACCTTGAGGACTTAGACAAACCTAGTACACAGGTGTA" 5 Returns: 11
Submissions are judged against all 59 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TandemRepeats with a public method int maxLength(string dna, int k) · 59 test cases · 2 s / 256 MB per case