C++ code [0ms; relatively clean for this problem]


  • 0
    M
            vector<string> generatePalindromes(string s)
            {
                // frequency count
                int freq[256] = { 0 };
                for (auto ch : s)
                    freq[ch]++;
    
                // add half counts of all chars, noting odd frequencies
                int oddcnt = 0;
                int center = -1;
    
                s.clear();
                for(int ch = 0; (ch < 256) && (oddcnt <= 1); ++ch)
                {
                    if (freq[ch] & 1)
                    {
                        center = ch;
                        oddcnt++;
                    }
    
                    freq[ch] /= 2;
                    s.append(freq[ch], ch);
                }
    
                if (1 < oddcnt)
                    return{};
    
                // get the unique half-palindromes
                unordered_set<string> pals;
                do {
                    pals.insert(s);
                } while (next_permutation(begin(s), end(s)));
    
                // generate the final palindrome set
                vector<string> res(begin(pals), end(pals));
                for (auto& s : res)
                {
                    auto N = s.size();
    
                    if (center != -1) 
                        s += center;
    
                    s.resize(s.size() + N);
                    reverse_copy(s.begin(), s.begin() + N, s.end() - N);
                }
    
                return res;
            }
    

Log in to reply
 

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