Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Repeticiones cortas en tándem del ADN (STR)

Para cada repetición corta en tándem, encuentra la serie más larga de copias seguidas dentro de una secuencia de ADN.

Lo que aprenderás

  • Comparar una subcadena con un patrón
  • Contar copias seguidas a partir de una posición
  • Guardar el mejor conteo de cada patrón

Problema

Ver original (inglés)

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

Ejemplo 1
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.

Ejemplo 2
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.