La sottostringa palindroma più lunga in una stringa in Java

La sottocadena palindroma più lunga in una stringa è una domanda di colloquio java molto comune. Per scoprire il palindromo più lungo in una Stringa, prima di tutto, dobbiamo identificare la logica per farlo.

Algoritmo della sottocadena palindroma più lunga in una stringa

Il punto chiave qui è che dal centro di qualsiasi stringa palindroma se ci spostiamo a destra e a sinistra di 1 posizione, è sempre lo stesso carattere. Ad esempio 12321, qui il centro è 3 e se continuiamo a spostarci di una posizione da entrambi i lati, otteniamo 2 e poi 1. Useremo la stessa logica nel nostro programma java per scoprire il palindromo più lungo. Tuttavia, se la lunghezza del palindromo è pari, anche la dimensione centrale è pari. Quindi dobbiamo assicurarci nel nostro programma che questo venga anche controllato. Ad esempio, 12333321, qui il centro è 33 e se continuiamo a spostarci di una posizione da entrambi i lati, otteniamo 3, 2 e 1.

Programma Java della sottocadena palindroma più lunga in una stringa

Nel nostro programma Java, itereremo sulla stringa di input con mid come primo carattere e verificheremo il carattere destro e sinistro. Avremo due variabili globali per salvare la posizione di inizio e fine per il palindromo. Dobbiamo anche verificare se è già stato trovato un palindromo più lungo poiché possono esserci più palindromi nella stringa data. Ecco il programma finale che funziona bene per tutti i casi.

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++) {
			//casi dispari come 121
			String palindrome = intermediatePalindrome(s, i, i);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
			//casi pari come 1221
			palindrome = intermediatePalindrome(s, i, i + 1);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
		}
		return longest;
	}

}

L’immagine sottostante mostra l’output del programma Java per il palindromo più lungo sopra. Possiamo migliorare il codice sopra spostando il controllo del palindromo e delle lunghezze più lunghe in una funzione diversa. Tuttavia, ho lasciato quella parte a te. 🙂 Per favore fammi sapere se ci sono altre implementazioni migliori o se fallisce in qualche caso.

Puoi scaricare l’esempio completo dal nostro Repository GitHub.