Problema
Compare two DNA strings position by position and count the differences. Only characters at the same position are compared; do not insert, delete, or shift characters. No biology knowledge is needed.
Implement hamming_distance(first, second).
Input
first: The first DNA string.
second: The equal-length second DNA string.
Output
Return the number of positions with different characters.
Restrições
Both strings have the same length, from 0 to 100,000. Characters are uppercase A, C, G, or T.
Exemplos
Entrada:
first = "ACCT"
second = "AGCA"
Saída esperada:
expected = 2Entrada:
std::string first = "ACCT";
std::string second = "AGCA";
Saída esperada:
long long expected = 2;Entrada:
string first = "ACCT";
string second = "AGCA";
Saída esperada:
long expected = 2;Explicação
The second position is C versus G and the fourth is T versus A. The first and third match: two differences.
Entrada:
first = "GATT"
second = "GATT"
Saída esperada:
expected = 0Entrada:
std::string first = "GATT";
std::string second = "GATT";
Saída esperada:
long long expected = 0;Entrada:
string first = "GATT";
string second = "GATT";
Saída esperada:
long expected = 0;Explicação
All four positions match, so no differences are counted.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Compare as duas strings posição por posição e conte quando os caracteres diferirem.
Dica 2
Uma única passada com iteração pareada basta; não é preciso reordenar nem buscar substrings.
Dica 3
Lembre que entradas com o mesmo tamanho ainda podem estar vazias, o que deve resultar em zero diferenças.
Complexidade esperada
tempo O(n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.