Problema
Laboratórios forenses comparam pessoas pelas repetições curtas em tandem (STRs, do inglês short tandem repeats): pequenas unidades de DNA, como AGAT, que aparecem muitas vezes seguidas. Para cada unidade, o laboratório registra a maior sequência de cópias consecutivas em qualquer ponto da sequência. Em TTAGATAGATAGATCAGATAGAT, a unidade AGAT aparece três vezes seguidas perto do início e duas vezes mais adiante, então a contagem dela é 3.
Implemente dna_str_count(sequence, repeats).
Entrada
sequence: a sequência de DNA, com as letras A, C, G e T.
repeats: as unidades STR a medir.
Saída
Retorne uma contagem por unidade, na mesma ordem de repeats: o maior número de cópias que aparecem uma logo depois da outra. Uma unidade que nunca aparece tem contagem 0.
Restrições
0 ≤ tamanho de sequence ≤ 5000
1 ≤ número de unidades ≤ 10
Cada unidade tem de 1 a 8 letras
Exemplos
Entrada:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]
Saída esperada:
expected = [3, 1]
Entrada:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};
Saída esperada:
std::vector<long long> expected = {3, 1};
Entrada:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};
Saída esperada:
long[] expected = new long[] {3, 1};
Explicação
AGAT aparece 3 vezes seguidas no início e só 2 no final, então vale 3; CA aparece uma vez, então vale 1.
Entrada:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]
Saída esperada:
expected = [3, 1, 0]
Entrada:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};
Saída esperada:
std::vector<long long> expected = {3, 1, 0};
Entrada:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};
Saída esperada:
long[] expected = new long[] {3, 1, 0};
Explicação
AATG se repete 3 vezes, TATC uma vez e GATA nenhuma: [3, 1, 0].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
A partir de uma posição inicial, continue avançando o tamanho da unidade enquanto o próximo trecho for igual à unidade.
Dica 2
Teste todas as posições iniciais e guarde a maior sequência.
Dica 3
Uma unidade que nunca aparece deixa a melhor contagem em 0.
Complexidade esperada
tempo O(n × m × k), espaço extra O(m)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.