Самая длинная подстрока-палиндром в строке на Java

Самая длинная подстрока-палиндром в строке – это очень распространенный вопрос на собеседованиях по Java. Чтобы найти самый длинный палиндром в String, прежде всего, нам нужно определить логику для его поиска.

Алгоритм поиска самой длинной подстроки-палиндрома в строке

Основной момент здесь заключается в том, что из середины любой строки-палиндрома, если мы двигаемся вправо и влево на 1 позицию, это всегда одинаковый символ. Например, 12321, здесь середина – 3, и если мы продолжим двигаться на одну позицию с обеих сторон, мы получим 2, а затем 1. Мы будем использовать ту же логику в нашей программе на Java, чтобы найти самый длинный палиндром. Однако, если длина палиндрома четна, то и середина тоже четна. Поэтому в нашей программе мы должны убедиться, что это тоже проверено. Например, 12333321, здесь середина – 33, и если мы будем двигаться на одну позицию с обеих сторон, мы получим 3, 2 и 1.

Программа на Java для поиска самой длинной подстроки-палиндрома в строке

В нашей программе на Java мы будем итерироваться по входной строке, начиная с середины, и проверять правый и левый символы. У нас будет две глобальные переменные для сохранения начальной и конечной позиции палиндрома. Нам также нужно проверить, был ли уже найден более длинный палиндром, поскольку в данной строке может быть несколько палиндромов. Вот окончательная программа, которая работает хорошо для всех случаев.

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++) {
			//нечетные случаи, например, 121
			String palindrome = intermediatePalindrome(s, i, i);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
			//четные случаи, например, 1221
			palindrome = intermediatePalindrome(s, i, i + 1);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
		}
		return longest;
	}

}

На изображении ниже показан результат работы вышеуказанной программы по поиску самого длинного палиндрома на Java. Мы можем улучшить этот код, переместив проверку палиндрома и самой длины в другую функцию. Однако я оставил эту часть за вами. 🙂 Пожалуйста, дайте знать, если есть какие-либо другие лучшие способы реализации или если он не работает в каком-либо случае.

Вы можете скачать полный пример кода из нашего репозитория GitHub.