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

• — Se o corredor entre as salas 4 e 5 estiver fechado, o visitante não pode receber um caminho antigo — explicou a…
• Uma estudante criou um programa para contar pontos em um jogo. Depois, percebeu que a mesma estrutura podia servir para…
• Projete a assinatura de um algoritmo que resolve várias instâncias de caminho mínimo: recebe um grafo e uma lista de…
• Projete a assinatura de um algoritmo generalizado chamado normalizar que aplica min–max scaling a um conjunto de…
• Compare três instâncias do problema de alocação de salas: instância A (30 turmas, horários fixos), B (45 turmas…
• No pseudocódigo de uma função que processa dados, qual termo descreve as condições que devem ser verdadeiras antes da…

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