Substring de palíndromo más largo en una cadena en Java

La subcadena de palíndromo más larga en una cadena es una pregunta de entrevista java muy común. Para descubrir el palíndromo más largo en una Cadena, primero que nada, necesitamos identificar la lógica para hacerlo.

Algoritmo de Subcadena de Palíndromo Más Largo en una Cadena

El punto clave aquí es que desde el medio de cualquier cadena de palíndromos, si vamos a la derecha y a la izquierda por 1 lugar, siempre es el mismo carácter. Por ejemplo 12321, aquí el medio es 3 y si seguimos moviéndonos una posición en ambos lados, obtenemos 2 y luego 1. Usaremos la misma lógica en nuestro programa java para descubrir el palíndromo más largo. Sin embargo, si la longitud del palíndromo es par, el tamaño medio también es par. Así que necesitamos asegurarnos en nuestro programa que esto también se verifica. Por ejemplo, 12333321, aquí el medio es 33 y si seguimos moviéndonos una posición en ambos lados, obtenemos 3, 2 y 1.

Programa Java de Subcadena de Palíndromo Más Largo en una Cadena

En nuestro programa Java, iteraremos sobre la cadena de entrada con ‘mid’ como la primera posición y comprobaremos el carácter derecho e izquierdo. Tendremos dos variables globales para guardar la posición de inicio y fin de un palíndromo. También necesitamos verificar si ya se ha encontrado un palíndromo más largo, ya que puede haber varios palíndromos en la cadena dada. Aquí está el programa final que funciona bien para todos los 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 impares 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;
	}

}

La siguiente imagen muestra la salida del anterior programa Java de palíndromo más largo. Podemos mejorar el código anterior moviendo la comprobación de palíndromos y longitudes más largas a una función diferente. Sin embargo, he dejado esa parte para ti. 🙂 Por favor, avísame si hay implementaciones mejores o si falla en algún caso.

Puedes descargar el código de ejemplo completo desde nuestro Repositorio de GitHub.