Problème
Les laboratoires de police scientifique comparent les individus grâce aux répétitions en tandem courtes (STR, short tandem repeats) : de courts motifs d'ADN, comme AGAT, qui se répètent de nombreuses fois à la suite. Pour chaque motif, le laboratoire relève la plus longue suite de copies consécutives dans toute la séquence. Dans TTAGATAGATAGATCAGATAGAT, le motif AGAT apparaît trois fois de suite près du début et deux fois plus loin, donc son compte est 3.
Implémentez dna_str_count(sequence, repeats).
Entrée
sequence : la séquence d'ADN, écrite avec les lettres A, C, G et T.
repeats : les motifs STR à mesurer.
Sortie
Renvoyez un compte par motif, dans le même ordre que repeats : le plus grand nombre de copies qui se suivent sans interruption. Un motif qui n'apparaît jamais a un compte de 0.
Contraintes
0 ≤ longueur de sequence ≤ 5 000
1 ≤ nombre de motifs ≤ 10
Chaque motif compte de 1 à 8 lettres
Exemples
Entrée :
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]
Sortie attendue :
expected = [3, 1]
Entrée :
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};
Sortie attendue :
std::vector<long long> expected = {3, 1};
Entrée :
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};
Sortie attendue :
long[] expected = new long[] {3, 1};
Explication
AGAT se répète 3 fois au début et seulement 2 fois à la fin, donc son score est 3 ; CA apparaît une fois, donc son score est 1.
Entrée :
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]
Sortie attendue :
expected = [3, 1, 0]
Entrée :
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};
Sortie attendue :
std::vector<long long> expected = {3, 1, 0};
Entrée :
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};
Sortie attendue :
long[] expected = new long[] {3, 1, 0};
Explication
AATG se répète 3 fois, TATC une fois et GATA jamais : [3, 1, 0].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
À partir d'une position de départ, avancez de la longueur du motif tant que le morceau suivant est égal au motif.
Indice 2
Essayez toutes les positions de départ et retenez la plus longue série.
Indice 3
Un motif qui ne correspond jamais laisse le meilleur compte à 0.
Complexité attendue
temps O(n × m × k), espace supplémentaire O(m)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.