c++ - 在不止一个回文的情况下寻找最长但字典序最小的回文

Question

给定一个字符串，我需要找到可以通过从字符串中删除或改组字符来构造的最长回文。如果存在多个相同长度的回文，那么我需要确保将字典序最小的回文作为输出给出。 示例:“adskassda” 预期输出为:“adsasda”

我能够找到最大的回文，但是如何确保在最大长度相同的倍数的情况下，字典序最小的一个作为输出给出？

任何回文字符串都可以分为三个部分——beg、mid 和 end。对于奇数长度的回文字符串，例如 2n + 1，'beg' 由字符串的前 n 个字符组成，'mid' 将仅由 1 个字符组成，即第 (n + 1) 个字符，'end' 将由最后 n 个字符组成的回文串。对于偶数长度为 2n 的回文字符串，'mid' 将始终为空。应该注意的是，'end'将与'beg'相反，以使字符串成为回文。 我也为此使用了相同的逻辑。

#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

你只有一个简单的错误。当你要选择中间的字符时，第一次看到频率为奇数的字符时，你应该选择它并且永远不要再次更新它，因为那将是字典序最低的那个。这就是我添加 bool 变量 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;
}