#include <iostream>

std::string output(int c, int s_idx, std::array<std::array<int, 20>, 26>& partials, std::array<int, 26> &freq, std::string &s) {
    if (s_idx == partials.size()) return "!";
    std::string ret = "!";

    while (s_idx < s.size() && freq[c] == 0) {
        s_idx += 1;
    }
    for (int c_idx = 0; c_idx < 26; c_idx += 1) {
        if (freq[c_idx] % 2 == 0) continue;
        if (partials[s_idx][c_idx] == 0) continue;

        std::string best = output(c_idx + 1, s_idx + 1, partials, freq, s);
        if (best != "!") {
            ret = char(c_idx + 'A') + best;
            break;
        }
    }
    return ret;
}

std::string solution(std::string s) {
    // Implement your solution here
    std::array<int, 26> freq = {};
    std::array<std::array<int, 20>, 26> partials = {};

    for (int idx = 0; idx < freq.size(); idx += 1) freq[idx] = 0;

    for (int idx = 0; idx < s.size(); idx += 1) {
        char ch = s[idx];
        if (idx > 0) {
            for (int c = 0; c < 26; c++) {
                partials[idx][c] = partials[idx - 1][c];
            }
        }
        partials[idx][ch - 'A'] += 1;
        freq[ch - 'A'] += 1;
    }

    for (auto c = 0; c < 26; c++) {
        std::cout << freq[c] << ", ";
    }

    for (auto c = 0; c < 26; c++) {
        for (auto i = 0; i < partials.size(); i++) {
            std::cout << partials[i][c] << ", ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;

    return output(0, 0, partials, freq, s);
}

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