BlackTDN :: LeetCode :: Desafio 5: Longest Palindromic Substring - Soluções em Harbour e Considerações

_Créditos das imagens: ChatGPT_

### LeetCode :: Desafio 5: Longest Palindromic Substring - Soluções em Harbour e Considerações

Encontrar a maior substring palindrômica dentro de uma string é um problema clássico de programação e lógica. [No desafio 5 do LeetCode](https://leetcode.com/problems/longest-palindromic-substring/description/) , abordamos esse problema implementando duas soluções distintas na linguagem Harbour. Este artigo apresenta uma análise detalhada das técnicas utilizadas, os resultados obtidos e comparações entre as abordagens.

#### Resumo do Problema
Um palíndromo é uma sequência de caracteres que pode ser lida da mesma forma de trás para frente. O objetivo do desafio é identificar a maior substring que seja um palíndromo dentro de uma string fornecida.

#### Código-Fonte
As implementações podem ser encontradas nos links abaixo:

- [Versão 5.1](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/hb/005/longest_palindromic_substring.5.1.prg)
- [Versão 5.2](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/hb/005/longest_palindromic_substring.5.2.prg)

#### Detalhes das Implementações
##### Versão 5.1
A abordagem da versão 5.1 utiliza uma verificação expandindo para fora de cada caractere ou par de caracteres ("centro do palíndromo"). Essa técnica permite explorar todas as possibilidades e encontrar substrings palindrômicas em tempo aceitável para entradas de tamanho moderado. Essa implementação:

- Verifica cada caractere e pares consecutivos como possíveis centros de palíndromos.
- Expande a verificação para os dois lados enquanto os caracteres forem iguais.
- Retorna o maior palíndromo encontrado.

##### Versão 5.2
A versão 5.2 utiliza o algoritmo de Manacher, uma técnica mais avançada e eficiente para encontrar a maior substring palindrômica em tempo linear. Além disso, essa versão também inclui o código da abordagem 5.1 para fins de comparação de resultados. Essa implementação:

- Garante maior eficiência em strings de grande tamanho.
- Fornece uma base mais robusta para analisar e validar os resultados da abordagem centrada.

#### Comparação entre as Abordagens
- **Eficiência**: A versão 5.2, que utiliza o algoritmo de Manacher, é significativamente mais rápida para strings grandes, pois opera em tempo linear. A versão 5.1 apresenta bom desempenho em strings moderadas, mas escala pior para entradas maiores devido à sua complexidade quadrática.
- **Simplicidade**: A versão 5.1 é mais intuitiva e fácil de implementar, ideal para quem está começando a explorar o problema. A versão 5.2 requer mais entendimento sobre algoritmos sofisticados.
- **Resultados adicionais**: Ambas as versões foram estendidas para não apenas encontrar o maior palíndromo, mas também identificar todas as substrings palindrômicas dentro da string.

#### Exemplos de Saída
Além de atender aos requisitos do desafio, os programas foram aprimorados para listar todas as palindromias possíveis dentro de uma palavra ou frase. Por exemplo:

1. Entrada: "Um relatório omissíssimo em vários pontos importantes."
   - Palíndromos: ["omississimo", "mississim", "ississi", "ssiss", "issi", "ss"]

2. Entrada: "Viajar para a cidade natal faz muitos reviverem memórias antigas."
   - Palíndromos: ["aja", "ara", "dad", "ata", "reviver", "evive", "viv", "ere", "mem"]
3. Outros Exemplos
```

+--------------------------------------------------------------------+-----------------------------------------------------------------------+
| Entrada                                                            | Palíndromos                                                           |
+--------------------------------------------------------------------+-----------------------------------------------------------------------+
| babad                                                              | ["bab", "aba"]                                                        |
| cbbd                                                               | ["bb"]                                                                |
| A Aia cuidava das crianças com dedicação.                          | ["Aia", "ava", "ded", "cac", "aca"]                                   |
| Quem tem aibofobia sente medo de palíndromos.                      | ["aibofobia", "ibofobi", "bofob", "ofo", "omo"]                       |
| A ala esquerda do prédio foi reformada.                            | ["ala", "ada"]                                                        |
| Ele ama viajar para lugares tranquilos.                            | ["Ele", "ama", "aja", "ara"]                                          |
| A cor foi obtida com anilina natural.                              | ["anilina", "nilin", "ili"]                                           |
| A ata da reunião foi enviada a todos os participantes.             | ["ata", "ada", "odo", "ici"]                                          |
| A arara azul é uma ave belíssima.                                  | ["arara", "rar", "ara", "issi", "ss"]                                 |
| O avião perdeu uma asa no acidente.                                | ["asa"]                                                               |
| Ele sempre está disposto a ajudar.                                 | ["Ele"]                                                               |
| Esse livro é um dos meus favoritos.                                | ["Esse", "ss"]                                                        |
| Os bebês mamam para se alimentar.                                  | ["beb", "ebe", "mamam", "ama", "mam", "ara"]                          |
| As ondas fortes matam muitos animais marinhos.                     | ["matam", "ata"]                                                      |
| Eles sempre metem o nariz onde não são chamados.                   | ["Ele", "metem", "ete", "ama"]                                        |
| O time mirim venceu o campeonato regional.                         | ["mirim", "iri"]                                                      |
| Um relatório omissíssimo em vários pontos importantes.             | ["omississimo", "mississim", "ississi", "ssiss", "issi", "ss"]        |
| Viajar para a cidade natal faz muitos reviverem memórias antigas.  | ["aja", "ara", "dad", "ata", "reviver", "evive", "viv", "ere", "mem"] |
| A discussão acalorada terminou em sopapos.                         | ["ss", "aca", "ada", "sopapos", "opapo", "pap"]                       |
+--------------------------------------------------------------------+-----------------------------------------------------------------------+ 

```

#### Conclusão
Ambas as soluções atendem plenamente aos requisitos do desafio, identificando a maior substring palindrômica. Além disso, ao listar todas as substrings palindrômicas, oferecem insights adicionais que podem ser úteis em aplicações práticas. A inclusão do algoritmo de Manacher na versão 5.2 permite explorar os limites do problema com eficiência e precisão.

Uma versão implementada em AdvPL/TLPP estará disponível em breve, ampliando o acesso à solução para diferentes comunidades de desenvolvedores.

#### Referências
- [Código-Fonte Versão 5.1](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/hb/005/longest_palindromic_substring.5.1.prg)
- [Código-Fonte Versão 5.2](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/hb/005/longest_palindromic_substring.5.2.prg)

#### Hashtags
#Palindromes #HarbourLanguage #AlgorithmDesign #LeetCodeSolutions #PalindromeSubstring #SoftwareDevelopment #ProgrammingChallenges #AdvPL #DynamicProgramming #CodeOptimization