Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.7 kB
1
Indexable
Never
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;
}