Problema
Los laboratorios forenses comparan a las personas mediante repeticiones cortas en tándem (STR, por sus siglas en inglés): unidades cortas de ADN, como AGAT, que aparecen muchas veces seguidas. Para cada unidad, el laboratorio registra la serie más larga de copias consecutivas en cualquier parte de la secuencia. En TTAGATAGATAGATCAGATAGAT, la unidad AGAT aparece tres veces seguidas cerca del inicio y dos veces más adelante, así que su conteo es 3.
Implementa dna_str_count(sequence, repeats).
Entrada
sequence: la secuencia de ADN, con las letras A, C, G y T.
repeats: las unidades STR que hay que medir.
Salida
Devuelve un conteo por unidad, en el mismo orden que repeats: la mayor cantidad de copias que aparecen una tras otra. Una unidad que nunca aparece tiene conteo 0.
Restricciones
0 ≤ longitud de sequence ≤ 5,000
1 ≤ número de unidades ≤ 10
Cada unidad tiene de 1 a 8 letras
Ejemplos
Entrada:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]
Salida esperada:
expected = [3, 1]
Entrada:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};
Salida esperada:
std::vector<long long> expected = {3, 1};
Entrada:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};
Salida esperada:
long[] expected = new long[] {3, 1};
Explicación
AGAT se repite 3 veces al inicio y solo 2 al final, así que su conteo es 3; CA aparece una vez, así que su conteo es 1.
Entrada:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]
Salida esperada:
expected = [3, 1, 0]
Entrada:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};
Salida esperada:
std::vector<long long> expected = {3, 1, 0};
Entrada:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};
Salida esperada:
long[] expected = new long[] {3, 1, 0};
Explicación
AATG se repite 3 veces, TATC una vez y GATA ninguna: [3, 1, 0].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Desde una posición inicial, sigue avanzando de a una unidad mientras el siguiente fragmento sea igual a la unidad.
Pista 2
Prueba todas las posiciones iniciales y guarda la serie más larga.
Pista 3
Si una unidad nunca coincide, el mejor conteo se queda en 0.
Complejidad esperada
tiempo O(n × m × k), espacio extra O(m)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.