#include <iostream>
#include <bitset>
#include <vector>
#include <array>
#include <cassert>

// zero_number_ascii_offset is an ascii number of '0' which is the offset for all ascii digits as well
constexpr char zero_number_ascii_offset = 48;

// typedef for single digits, just a presence of a digit
typedef std::bitset<10> singles_t;
// typedef for counts of doubles digits
typedef std::array<size_t, 10> doubles_t;

// to_digit converts char to digit
uint8_t to_digit(char c) {
    return c - zero_number_ascii_offset;
}

// to_char converts digit to char
char to_char(uint8_t n) {
    return n + zero_number_ascii_offset;
}

/* solution
 * let's assume the biggest palindrome has:
 * 1. biggest single in the center (xxx9xxx > xxx8xxx);
 * 2. biggest doubles at corners (9xxxx9 > 8xxxx8).
 *
 * the algorithm:
 * 1. count all doubles and singles, takes O(N);
 * 2. construct the result string with constant length;
 * 3. if there is biggest single then put it to the center;
 * 4. fill the string from the center to corners using doubles;
 *
 * complexity: O(N)
 */
std::string solution(std::string &S) {

    std::bitset<10> singles{};
    std::array<size_t, 10> doubles{};

    size_t doubles_count = 0;
    size_t doubles_sum = 0;

    for (char c: S) {
        uint8_t digit = to_digit(c);

        assert(digit < 10);

        if (singles.test(digit)) {
            singles.reset(digit);
            ++doubles[digit];
            ++doubles_count;
            doubles_sum += digit;
        } else {
            singles.set(digit);
        }
    }

    char biggest_single = 0;
    for (uint8_t i = 10; i > 0; i--) {
        if (singles.test(i - 1)) {
            biggest_single = to_char(i - 1);
            break;
        }
    }

    bool has_single = biggest_single > 0;
    size_t single_offset = (has_single ? 1 : 0);
    size_t result_len = doubles_count * 2 + single_offset;
    if (doubles_sum == 0) {
        result_len = 1;
        biggest_single = biggest_single > 0 ? biggest_single : '0';
    }

    std::string result(result_len, biggest_single);

    if (doubles_sum > 0) {
        size_t iter = 0;
        for (uint8_t i = 0; i < 10; i++) {
            size_t count = doubles[i];
            while (count-- > 0) {
                result[result_len / 2 - 1 - iter] = to_char(i);
                result[result_len / 2 + single_offset + iter] = to_char(i);
                iter++;
            }
        }
    }

    return result;
}

int main() {
    std::cout << solution("090") << std::endl;
    return 0;
}