# permutation with duplication + valid parlidrome string

• ``````class Solution {
public:
vector<string> generatePalindromes(string s) {
int freq[126] = {0};
for (char &ch:s) ++freq[ch];
int odd = 0, oindx = -1;
for (int i = 0; i < 126; ++i) {
if (freq[i]&0x1) {
++odd; oindx = i;
}
}
if (odd > 1) {
return vector<string> {};
}
string half;
for (int i = 0; i < 126; ++i) {
if (freq[i] && freq[i] >= 2) half += string(freq[i]/2, char(i));
}
sort(half.begin(), half.end());
vector<string> rst;
generate(rst, half, 0, oindx);

return rst;
}
void generate(vector<string> &rst, string &half, int indx, int oindx) {
if (indx == half.size()) {
string rev = half;
reverse(rev.begin(), rev.end());
rst.emplace_back(oindx >= 0 ? half+string(1, oindx)+rev:half+rev);
return;
}
unordered_set<char> visited;
for (int i = indx; i < half.size(); ++i) {
if (visited.find(half[i]) != visited.end()) continue;
visited.insert(half[i]);
swap(half[i], half[indx]);
generate(rst, half, indx+1, oindx);
swap(half[i], half[indx]);
while (i+1 < half.size() && half[i+1] == half[i]) ++i;
}
}
};
``````

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