# Short < 20 lines C++ modulized solution

• Steps:

1. Generate string `half` with half char frequency from `s`.
2. Generate all permutations of string `half`.
3. Construct palindromes from each permutation of `half`.
``````    vector<string> perms; // all permutations

vector<string> generatePalindromes(string s) {
string c;  if (!half(s, c)) return {};
genPerms(s, 0);
for (auto& str : perms)
str += c + string(str.rbegin(), str.rend());
return perms;
}

// get half frequency string and central char
bool half(string& s, string& c) {
unordered_map<char, int> fre;
for (char ch : s) ++fre[ch]; s = "";
for (auto& p : fre)
if ((c += string(p.second%2, p.first)).size() > 1) return false;
else s += string (p.second/2, p.first);
return true;
}

// Permutation II: generate all permutations for s
void genPerms(string s, int i) {
if (i+1 >= s.size())
perms.push_back(s);
else for (int j = i; j < s.size(); ++j) {
if (j > i && s[j] == s[i]) continue;
swap(s[i], s[j]);
genPerms(s, i+1);
}
}
``````

• @zzg_zzm
your function genPerms generates duplicates, try a test case genPerms("ABCB", 0)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.