Plus longue sous-chaîne palindrome dans une chaîne en Java

La plus longue sous-chaîne palindrome dans une chaîne est une question d’entretien java très courante. Pour trouver la plus longue palindrome dans une chaîne de caractères, tout d’abord, nous devons identifier la logique pour le faire.

Algorithme de la plus longue sous-chaîne palindrome dans une chaîne de caractères

Le point clé ici est que du milieu de n’importe quelle sous-chaîne palindrome, si nous nous déplaçons d’une position vers la droite et vers la gauche, nous obtenons toujours le même caractère. Par exemple, 12321, ici le milieu est 3 et si nous continuons de bouger d’une position des deux côtés, nous obtenons 2 et ensuite 1. Nous utiliserons la même logique dans notre programme java pour trouver la plus longue palindrome. Cependant, si la longueur du palindrome est paire, la taille du milieu est également paire. Nous devons donc nous assurer dans notre programme que cela est également vérifié. Par exemple, 12333321, ici le milieu est 33 et si nous continuons de bouger d’une position des deux côtés, nous obtenons 3, 2 et 1.

Programme Java pour la plus longue sous-chaîne palindrome dans une chaîne de caractères

Dans notre programme Java, nous allons itérer sur la chaîne d’entrée avec le milieu comme première position et vérifier le caractère de droite et de gauche. Nous aurons deux variables globales pour enregistrer la position de début et de fin du palindrome. Nous devons également vérifier s’il existe déjà un palindrome plus long, car il peut y avoir plusieurs palindromes dans la chaîne donnée. Voici le programme final qui fonctionne bien pour tous les cas.

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++) {
			//cas impairs comme 121
			String palindrome = intermediatePalindrome(s, i, i);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
			//cas pairs comme 1221
			palindrome = intermediatePalindrome(s, i, i + 1);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
		}
		return longest;
	}

}

L’image ci-dessous montre la sortie du programme Java de plus long palindrome. Nous pouvons améliorer le code ci-dessus en déplaçant la vérification du palindrome et de la longueur maximale dans une fonction différente. Cependant, j’ai laissé cette partie pour vous. 🙂 Veuillez me faire savoir s’il existe d’autres meilleures implémentations ou si elle échoue dans un cas quelconque.

Vous pouvez télécharger le code d’exemple complet depuis notre Dépôt GitHub.