Projete um algoritmo em pseudocódigo que receba como dado de entrada uma string binária s (composta por '0' e…

Questão

Projete um algoritmo em pseudocódigo que receba como dado de entrada uma string binária s (composta por '0' e '1') e uma variável k (inteiro par > 0). O algoritmo deve retornar verdadeiro se existir em s uma substring de comprimento k que contenha exatamente k/2 caracteres '1', e falso caso contrário. Explique a abordagem e a complexidade.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo (janela deslizante) Entrada: s (string de '0'/'1'), k (inteiro par) se k <= 0 ou k > comprimento(s) então retornar falso fim se contador1 <- 0 // inicializa contagem na primeira janela para i de 0 até k-1 faça se s[i] == '1' então contador1 <- contador1 + 1 fim para se contador1 == k/2 então retornar verdadeiro // desliza a janela para i de k até comprimento(s)-1 faça se s[i] == '1' então contador1 <- contador1 + 1 se s[i-k] == '1' então contador1 <- contador1 - 1 se contador1 == k/2 então retornar verdadeiro fim para retornar falso Abordagem e complexidade: Usa-se técnica de janela deslizante para manter a contagem de '1' em cada substring de comprimento k atualizando-a em tempo constante quando a janela avança. A inicialização custa O(k) e cada deslize custa O(1), totalizando O(n) tempo para n = comprimento(s). A memória extra é O(1) (apenas variáveis de contagem e índices).

Explicação

A abordagem de janela deslizante permite verificar eficientemente todas as substrings de comprimento k, mantendo a contagem de '1's atualizada com operações de tempo constante. Isso garante que o algoritmo percorra a string apenas uma vez, resultando em uma complexidade linear. A utilização de variáveis de contagem minimiza o uso de memória, tornando a solução eficiente em termos de recursos.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo em pseudocódigo que, dado um vetor V de n inteiros e um inteiro k, determine se existem índices i <…
• Escreva um algoritmo em pseudocódigo que receba uma sequência de bits (entrada) e gere um bit de paridade ímpar…
• Proponha um algoritmo em pseudocódigo que, dada uma lista A de n inteiros e um inteiro k>0, determine o comprimento do…
• Projete um algoritmo em pseudocódigo que, dada uma matriz M[m][n] de inteiros (valores 0/1) e um inteiro k>0, retorne o…
• Descreva um algoritmo em pseudocódigo que, dado n variáveis booleanas (dados de entrada), gere todas as 2^n combinações…
• Projete um algoritmo em pseudocódigo que, dada uma árvore enraizada representada por nós com referências a filhos e uma…

Todas as questões de Estratégias de solução de problemas - Generalização