Javaで文字列内の最長回文部分文字列

文字列内の最長の回文部分文字列は、非常に一般的なJavaの面接問題です。文字列内の最長の回文を見つけるには、まず、それを行うためのロジックを特定する必要があります。

文字列内の最長の回文部分文字列のアルゴリズム

ここでの鍵となるポイントは、回文の文字列の中央からそれぞれ右と左に1つずつ進んだ場合、常に同じ文字になるということです。例えば12321の場合、中央は3であり、両側に1つずつ進むと、2、1となります。このロジックをJavaのプログラムで最長の回文を見つけるために使用します。ただし、回文の長さが偶数の場合、中央の位置も偶数になります。したがって、プログラム内でこれも確認する必要があります。例えば、12333321の場合、中央は33であり、両側に1つずつ進むと、3、2、1となります。

文字列内における最長の回文の部分文字列を見つけるためのJavaプログラム

私たちのJavaプログラムでは、入力文字列を中央（mid）を1番目の位置として反復処理し、右と左の文字をチェックします。パリンドロームの開始位置と終了位置を保存するために2つのグローバル変数が必要です。また、指定された文字列には複数のパリンドロームが存在することがあるため、既に長いパリンドロームが見つかっているかどうかも確認する必要があります。すべてのケースに対して正常に動作する最終プログラムは次のとおりです。

package com.scdev.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++) {
			//odd cases like 121
			String palindrome = intermediatePalindrome(s, i, i);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
			//even cases like 1221
			palindrome = intermediatePalindrome(s, i, i + 1);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
		}
		return longest;
	}

}

弊社のGitHubリポジトリから、完全なサンプルコードをダウンロードできます。