Problema
Um laboratório de probabilidade lança uma moeda muitas vezes e anota os resultados como uma string de H (cara) e T (coroa). Uma sequência é um grupo máximo de resultados iguais consecutivos; HHTHHH tem as sequências HH, T e HHH. Os alunos costumam se surpreender com o tamanho da maior sequência em um registro aleatório, então o laboratório mede isso.
Implemente coin_toss_streaks(tosses).
Entrada
tosses: os resultados em ordem, usando apenas H e T.
Saída
Retorne [longest_heads, longest_tails, streaks]: o tamanho da maior sequência de caras, o tamanho da maior sequência de coroas (0 se esse lado nunca sair) e o número total de sequências.
Restrições
0 ≤ tamanho de tosses ≤ 100 000
Exemplos
Entrada:
tosses = "HHTHHH"
Saída esperada:
expected = [3, 1, 3]
Entrada:
std::string tosses = "HHTHHH";
Saída esperada:
std::vector<long long> expected = {3, 1, 3};
Entrada:
string tosses = "HHTHHH";
Saída esperada:
long[] expected = new long[] {3, 1, 3};
Explicação
As sequências são HH, T e HHH, então a maior sequência de caras tem 3, a maior de coroas tem 1, e há 3 sequências.
Entrada:
tosses = "TTTT"
Saída esperada:
expected = [0, 4, 1]
Entrada:
std::string tosses = "TTTT";
Saída esperada:
std::vector<long long> expected = {0, 4, 1};
Entrada:
string tosses = "TTTT";
Saída esperada:
long[] expected = new long[] {0, 4, 1};
Explicação
Cara nunca sai, então a maior sequência de caras é 0; há uma sequência de coroas de tamanho 4: [0, 4, 1].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Uma nova sequência começa no índice 0 e em todo ponto em que um lançamento é diferente do anterior.
Dica 2
Guarde um melhor tamanho para as caras e outro para as coroas.
Dica 3
Uma string vazia não tem nenhuma sequência.
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.