Maior Substring Palíndromo em uma String em Java

A substring de palíndromo mais longa em uma string é uma pergunta muito comum em entrevistas de emprego de Java. Para encontrar a substring de palíndromo mais longa em uma String, primeiro precisamos identificar a lógica para fazê-lo.

Algoritmo para encontrar a substring de palíndromo mais longa em uma String

O ponto chave aqui é que, a partir do meio de qualquer string palíndromo, se avançarmos uma posição para a direita e uma posição para a esquerda, sempre obteremos o mesmo caractere. Por exemplo, na string 12321, o meio é 3 e, se avançarmos uma posição em ambos os lados, obtemos 2 e depois 1. Usaremos a mesma lógica em nosso programa Java para encontrar a substring de palíndromo mais longa. No entanto, se o comprimento do palíndromo for par, o tamanho do meio também será par. Portanto, precisamos garantir em nosso programa que isso também seja verificado. Por exemplo, na string 12333321, o meio é 33 e, se avançarmos uma posição em ambos os lados, obtemos 3, 2 e 1.

Programa Java para encontrar a substring de palíndromo mais longa em uma String

No nosso programa Java, iremos iterar sobre a string de entrada com o meio como primeira posição e verificar o caractere à direita e à esquerda. Teremos duas variáveis globais para salvar a posição inicial e final do palíndromo. Também precisamos verificar se já foi encontrado um palíndromo mais longo, pois pode haver múltiplos palíndromos na string fornecida. Aqui está o programa final que funciona bem para todos os casos.

package com.journaldev.util;

public class LongestPalindromeFinder {

	public static void main(String[] args) {
		System.out.println(longestPalindromeString("1234"));
		System.out.println(longestPalindromeString("12321"));
		System.out.println(longestPalindromeString("9912321456"));
		System.out.println(longestPalindromeString("9912333321456"));
		System.out.println(longestPalindromeString("12145445499"));
		System.out.println(longestPalindromeString("1223213"));
		System.out.println(longestPalindromeString("abb"));
	}

	static public String intermediatePalindrome(String s, int left, int right) {
		if (left > right) return null;
		while (left >= 0 && right < s.length()
				&& s.charAt(left) == s.charAt(right)) {
			left--;
			right++;
		}
		return s.substring(left + 1, right);
	}

	// O(n^2)
	public static String longestPalindromeString(String s) {
		if (s == null) return null;
		String longest = s.substring(0, 1);
		for (int i = 0; i < s.length() - 1; i++) {
			//casos ímpares como 121
			String palindrome = intermediatePalindrome(s, i, i);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
			//casos pares como 1221
			palindrome = intermediatePalindrome(s, i, i + 1);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
		}
		return longest;
	}

}

A imagem abaixo mostra a saída do programa Java de palíndromo mais longo acima. Podemos melhorar o código acima movendo a verificação de palíndromo e comprimento mais longo para uma função diferente. No entanto, deixei essa parte para você. 🙂 Por favor, me avise se houver implementações melhores ou se falhar em algum caso.

Você pode baixar o código de exemplo completo do nosso Repositório GitHub.