Нахождение самого длинного, но лексикографически самого маленького палиндрома в случае более чем одного палиндрома

Question

Учитывая строку, мне нужно найти самый длинный палиндром, который можно построить, удалив или перетасовав символы из строки. Если существует более одного палиндрома одинаковой длины, мне нужно убедиться, что лексикографически наименьший из них указан в качестве выходного. Пример: "adskassda" Ожидаемый результат: "adsasda"

Я могу найти самый большой палиндром, но как обеспечить, чтобы в случае кратных одной и той же максимальной длины лексикографически наименьший был выдан в качестве выхода?

Любую палиндромную струну можно разделить на три части - начальная, средняя и конечная. Для палиндромной строки нечетной длины, скажем, 2n + 1, «beg» состоит из первых n символов строки, «mid» будет состоять только из 1 символа, т.е. (n + 1) -й символ, а «end» будет состоять из последних n символов палиндромной струны. Для палиндромной струны четной длины 2n 'mid' всегда будет пустым. Следует отметить, что «конец» будет обратным «умолять», чтобы строка была палиндромом. Я тоже использовал ту же логику для этого.

#include <bits/stdc++.h>
using namespace std;

string longestPalindrome(string str){
    map<char,int> frequencyChar;
    for(int i=0;i<str.length();i++){
        frequencyChar[str[i]]++;
    }
    char middle_character;
    string leftStr;
    for(auto it: frequencyChar){
        char currentChar=it.first;
        int frequencyCurrentChr = it.second;
        if(frequencyCurrentChr%2!=0){
            middle_character=currentChar;
        }
        leftStr.append(frequencyCurrentChr/2,currentChar);
    }
    string rightStr(leftStr.rbegin(),leftStr.rend());
    return leftStr + middle_character + rightStr;
}
int main() {
    string str = "adskassda";
    cout<<longestPalindrome(str);
}

Я получаю "adsssda", но ожидается "adsasda"

Answer 1

У вас есть только простая ошибка.Если вы хотите выбрать средний символ, когда вы впервые видите его с нечетной частотой, вы должны выбрать его и никогда не обновлять, потому что это будет тот, который имеет самый низкий лексикографический порядок.Вот почему я добавил логическую переменную mid_char_chosen, и когда она установлена ​​в значение true, она больше не будет обновляться.Есть еще один угловой случай, который вы еще не рассматривали: если все частоты равны, тогда не будет среднего символа, а результат будет иметь четное количество символов.Таким образом, вывод должен опускать средний символ.С этими незначительными изменениями, я думаю, что код работает:

#include <bits/stdc++.h>
using namespace std;

string longestPalindrome(string str){
    map<char,int> frequencyChar;
    for(int i=0;i<str.length();i++){
        frequencyChar[str[i]]++;
    }
    char middle_character;
    string leftStr;
    bool mid_char_chosen = false;
    for(auto it: frequencyChar){
        char currentChar=it.first;
        int frequencyCurrentChr = it.second;
        if(!mid_char_chosen and frequencyCurrentChr%2!=0){
            middle_character=currentChar;
            mid_char_chosen = true;
        }
        leftStr.append(1*(frequencyCurrentChr/2),currentChar);
    }
    string rightStr(leftStr.rbegin(),leftStr.rend());
    if (mid_char_chosen)
        return leftStr + middle_character + rightStr;
    else
        return leftStr +  rightStr;
}
int main() {
    string str = "adskassda";
    cout<<longestPalindrome(str) << endl;
}

Answer 2

Мне показалось, что это работает, хотя мое тестирование было далеко не полным:

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

int main()
{
    string in("adskassda");
    map<char, int> chars;
    string out;

    for (auto c : in)
    {
        ++chars[c];
    }

    string middle;
    for (auto e : chars)
    {
        if (e.second >= 2)
        {
            out.append(e.second/2, e.first);
            e.second = e.second%2;
        }

        if (e.second && middle.empty())
            middle = e.first;
    }

    string tail(out);
    reverse(tail.begin(), tail.end());
    out = out + middle + tail;

    cout << in << endl;
    cout << out << endl;
}