string solution(string &s) {
vector<char> substrings(s.size() * 2 + 1, '#');
for(int i = 0; i != s.size(); ++i){
substrings[i*2 + 1] = s[i];
}
int palindromeRadius[substrings.size()];
int radius = 0;
int center = 0;
int index = 0;
int i_mir = 0;
int maxLen = 1;
for(int i = 1; i != substrings.size() - 1; ++i){
i_mir = 2*center - i;
palindromeRadius[i] = radius > i ? min(palindromeRadius[i_mir], radius - i) : 0;
while(i > palindromeRadius[i] && (i + palindromeRadius[i] + 1) < substrings.size() && substrings[i - palindromeRadius[i] - 1] == substrings[i + palindromeRadius[i] + 1])
++palindromeRadius[i];
if(palindromeRadius[i] + i > radius){
center = i;
radius = i + palindromeRadius[i];
}
if(maxLen < palindromeRadius[i]){
maxLen = palindromeRadius[i];
index = i;
}
}
string result = s.substr((index - maxLen) / 2, maxLen);
string changedResult = result;
for(int i = 0; i < result.size() / 2; ++i) {
if(result[i] - '0' == 0) {
changedResult = result.substr(i + 1, result.size() - 2*(i + 1));
}
}
if(changedResult != result) {
if(changedResult.empty()) {
result = "0";
}
else {
result = changedResult;
}
}
else if(result.size() == 1) {
int intRes = 0;
for(int i = 0; i < s.size(); ++i) {
if(s[i] - '0' > intRes) {
result = s[i];
intRes = s[i] - '0';
}
}
}
return result;
}