Solução Informática Iniciante – Semana 51 – Problema 1

Solução por Lúcio Cardoso

Para checar se uma string $$S$$ qualquer é um palíndromo, basta checar se o caractere de cada posição $$i$$ em $$S$$ é igual ao caractere na mesma posição $$i$$ da string reversa de $$S$$. Logo, é possível realizar a checagem em $$O(N)$$, onde $$N$$ é o tamanho da string.

Pela definição do problema, queremos encontrar a maior substring (string formada por posições consecutivas da palavra original) que é um palíndromo. Podemos então checar todas as $$O(n^2)$$ substrings com o algoritmo descrito acima em $$O(n)$$, atualizando a maior resposta caso a substring seja um palíndromo. A complexidade final será então $$O(n^3)$$.

Confira o código abaixo para melhor entendimento:

https://gist.github.com/luciocf/7b3bc85c888e4d64d5f38f00cb1432a0