public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String inputStr = scanner.next();
String result = findPalindromeSubstring(inputStr);
System.out.println(result);
}
public static String findPalindromeSubstring(String inputStr) {
int maxLength = 0;
String longestPalindrome = "";
for (int i = 0; i < inputStr.length(); i++) {
// 奇數長度的迴文,以 i 為中心
String palindromeOdd = expandAroundCenter(inputStr, i, i);
if (palindromeOdd.length() > maxLength) {
maxLength = palindromeOdd.length();
longestPalindrome = palindromeOdd;
}
// 偶數長度的迴文,以 i 和 i+1 為中心
String palindromeEven = expandAroundCenter(inputStr, i, i + 1);
if (palindromeEven.length() > maxLength) {
maxLength = palindromeEven.length();
longestPalindrome = palindromeEven;
}
}
return maxLength > 1 ? longestPalindrome : "None";
}
public static String expandAroundCenter(String str, int left, int right) {
while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
left--;
right++;
}
return str.substring(left + 1, right);
//從 left 的下一個位置開始,到 right 位置之前(不包含 right 位置),所對應的字串,即為最終的迴文子字串
}
}
Time: O(n^2) Space: O(n^2)