Escreva um algoritmo em pseudocódigo que receba uma string (entrada) e devolva sua codificação por run-length…

Questão

Escreva um algoritmo em pseudocódigo que receba uma string (entrada) e devolva sua codificação por run-length encoding (RLE). O algoritmo deve codificar sequências consecutivas de um mesmo caractere como caractere seguido da contagem; inclua um exemplo de entrada e saída.

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

Resposta esperada

Algoritmo RLE(s: string) -> string: if s == "" then return "" result <- "" count <- 1 for i from 1 to length(s)-1 do if s[i] == s[i+1] then count <- count + 1 else result <- result + s[i] + toString(count) count <- 1 end if end for result <- result + s[length(s)] + toString(count) return result Explicação: o algoritmo percorre a string uma vez, conta repetições consecutivas e concatena o caractere com sua contagem quando muda o caractere seguinte; complexidade O(n). Exemplo: entrada "AAAABBBCC" -> saída "A4B3C2". Opcionalmente, separar pares com delimitador (ex.: "A:4;B:3;C:2") se for necessário evitar ambiguidade entre caracteres e dígitos.

Explicação

O algoritmo eficientemente percorre a string uma única vez, garantindo que cada caractere e sua contagem sejam processados em tempo linear. A lógica de contagem e concatenação permite a construção da string codificada de maneira clara e direta. A complexidade O(n) assegura que a solução é escalável para strings de diferentes tamanhos.

Raio-X da questão

Questões parecidas com resolução

• Em uma usina, cada estado de uma turbina é registrado com um código de dois bits: | Estado | Código | |---|---| | Parada…
• No controle de um satélite, um gráfico de barras descrito pela equipe registra: com o sistema operacional iniciado, o…
• O clube de jogos da escola vai usar um programa simples para registrar cada participante. Em cada cadastro, a pessoa…
• Na horta da escola, uma estação simples registra a temperatura informada por um sensor. O programa deve mostrar essa…
• Pesquisadores acompanham o funcionamento de um robô que cuida de seis placas solares em uma estação de pesquisa. O robô…
• Por que alguns tablets de um centro cultural aparecem como disponíveis, embora estejam guardados para conserto? Para…

Todas as questões de Programação - Linguagem de programação