Todos os desafios
Médio 0 resolvidos 0% de aceitação

Repetições curtas em tandem (STR) no DNA

Para cada repetição curta em tandem, encontre a maior sequência de cópias seguidas em uma sequência de DNA.

O que você vai aprender

  • Comparar uma substring com um padrão
  • Contar cópias seguidas a partir de uma posição
  • Guardar a melhor contagem de cada padrão

Problema

Ver original (inglês)

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

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

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.