public class Main {
if(s == null || s.length() <= 1)
return s;
int[] lp = new int[s.length()];
int maxIdx = 0;
for(int i = 0; i < s.length(); i++) {
lp[i] = 1;
if(i == 0)
continue;
if(lp[i-1] == 1 && s.charAt(i) == s.charAt(i-1))
lp[i] = 2;
else if(i - lp[i-1] - 1 >= 0 && s.charAt(i) == s.charAt(i - lp[i-1] - 1))
lp
[i
] = Math.
max(lp
[i
], lp
[i
-1] + 2); if(lp[i] > lp[maxIdx])
maxIdx = i;
}
return s.substring(maxIdx - lp[maxIdx] + 1, maxIdx + 1);
}
public static void main
(String[] args
) { System.
out.
println(largestPalindrome
("madamimada1")); }
}
cHVibGljIGNsYXNzIE1haW4gewogICAgcHVibGljIHN0YXRpYyBTdHJpbmcgbGFyZ2VzdFBhbGluZHJvbWUoU3RyaW5nIHMpIHsKICAgICAgICBpZihzID09IG51bGwgfHwgcy5sZW5ndGgoKSA8PSAxKQogICAgICAgICAgIHJldHVybiBzOwogICAgICAgICAgIAogICAgICAgIGludFtdIGxwID0gbmV3IGludFtzLmxlbmd0aCgpXTsKICAgICAgICBpbnQgbWF4SWR4ID0gMDsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgcy5sZW5ndGgoKTsgaSsrKSB7CiAgICAgICAgICAgIGxwW2ldID0gMTsKCiAgICAgICAgICAgIGlmKGkgPT0gMCkKICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgICAKICAgICAgICAgICAgaWYobHBbaS0xXSA9PSAxICYmIHMuY2hhckF0KGkpID09IHMuY2hhckF0KGktMSkpCiAgICAgICAgICAgICAgICAgICAgbHBbaV0gPSAyOwogICAgICAgICAgICBlbHNlIGlmKGkgLSBscFtpLTFdIC0gMSA+PSAwICYmIHMuY2hhckF0KGkpID09IHMuY2hhckF0KGkgLSBscFtpLTFdIC0gMSkpCiAgICAgICAgICAgICAgICBscFtpXSA9IE1hdGgubWF4KGxwW2ldLCBscFtpLTFdICsgMik7CiAgICAgICAgICAgaWYobHBbaV0gPiBscFttYXhJZHhdKQogICAgICAgICAgICAgbWF4SWR4ID0gaTsKICAgICAgICB9IAogICAgICAgIHJldHVybiBzLnN1YnN0cmluZyhtYXhJZHggLSBscFttYXhJZHhdICsgMSwgbWF4SWR4ICsgMSk7CiAgICB9CiAgICAKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4obGFyZ2VzdFBhbGluZHJvbWUoIm1hZGFtaW1hZGExIikpOwogICAgfQp9