Palindrome reconstruction - please help !!!

[kizhvac kampazitr]

Palindrome reconstruction

You are given a word consisting of lowercase Latin letters. You need to rearrange the letters of the word so that a palindrome results. If there are several possible resulting palindromes, output the lexicographically smallest one (the one that would come first in a standard dictionary). If it is impossible to rearrange the letters into a palindrome, output the word “impossible”.

can only use iostream, string, vector, algorithm

dblolod - dlobold
abababcd - impossible
abababbacadacad - aaabbcdadcbbaaa

I want to write function to make string palindrome

  #include <iostream>
#include <string>
#include <algorithm>

//dblolod - bddlloo - dlobold  

void CountingSort(std::string& s)
{
	std::string buckets;
	for(int i = 0; i < s.size(); ++i)
		++buckets[s[i] - 'a'];
	s.clear();
	for(int i = 0; i < buckets.size(); ++i)
		for(int j = 0; j < buckets[i]; ++j)
			s.push_back(i);
}

void make_palindrome(std::string& s)
{
	
}

int main()
{
	std::string letters;
	std::cin >> letters;
	CountingSort(letters);
	make_palindrome(letters);
	std::cout << letters;
}

[lastchance]

Possible route (there are several):

- sort the string (use the standard sort() algorithm, not your CountingSort)

- it will be possible to make a palindrome if ... the string is even length and no unpaired letters OR the string is odd length and there is precisely one unmatched letter (for convenience, move this to the end of the string);

- return bool false if you can't make a palindrome;

- otherwise take the successive pairs in your sorted string and assign them to start and end of a new string of the correct length

- if of odd length then put the single unmatched letter in the middle of the new string.

[kizhvac kampazitr]

lastchance The fact is that they told us to use CountingSort
But for everything else, thanks

[lastchance]

Well, you create a string of zero size in line 9, but write beyond the bounds of this string in line 11.

Just saying.

[kizhvac kampazitr]

Yes, the thing is that I can not set the size )))

[Enoizat]

they told us to use CountingSort

Does it means you were expected to write a function called "CountingSort()" or you are required to use that specific CountingSort() written above?
Because that version of CountingSort() doesn't look so useful.

I've added some 'cout(s)' to show it's mechanism, which is pretty mysterious to me:

#include <iostream>
#include <string>
#include <algorithm>

//dblolod - bddlloo - dlobold  

void CountingSort(std::string& s);
void make_palindrome(std::string& s);

int main()
{
    std::cout << "\nPlease, insert a word: ";
    std::string letters;
    std::cin >> letters;
    CountingSort(letters);
    //make_palindrome(letters);
    std::cout << letters;

    return 0;
}

void CountingSort(std::string& s)
{
    std::string buckets;
    for(int i = 0; i < s.size(); ++i) {
        ++buckets[s[i] - 'a']; // = ?
        std::cout << "buckets[s[" << i << "] - 'a'] == " 
                  << buckets[s[i] - 'a']
                  << '\n';
    }

    s.clear(); // ???

    std::cout << "\nbuckets.lenght() == " << buckets.length()
              << "; s.lenght() == " << s.length() << "\n\n";

    for(int i = 0; i < buckets.size(); ++i) {
        for(int j = 0; j < buckets[i]; ++j) {
            s.push_back(i);
            std::cout << "i == " << i 
                      << "; s.push_back(i); == " << s.at(s.length()-1)
                      << '\n';
        }
    }

    std::cout << "At the end if the day, buckets == '" << buckets
              << "' and s == '" << s << "'\n";
}

void make_palindrome(std::string& s)
{}

[lastchance]

@kizhvac kampazitr

Could you state precisely your problem (I'll assume it's an assignment) - especially where it says you need to use Counting Sort.

If you need to count letters of each type then you would increment an integer array, not a string; say:

int buckets[26] = { 0 };   // you say latin letters, although from your name it might not be your alphabet;
// .....
++buckets[s[i] - 'a'];

You could go on to complete the sorting of s, although it would be, e.g.,
s.push_back((char)('a'+i));

Equally, however, you could go straight on to try to construct the palindrome directly from your buckets[] array instead of the sorted string. For even counts in a bucket, assemble half this number of characters from the front and half from the back of the palindrome. For odd counts (and there may be at most one, and then only for an odd-length string) put this character in the middle of the palindrome.

The key thing, however, is that if you intend to do any counting, then buckets[] needs to be an integer array; (or a map, but that's probably making things unnecessarily difficult).

[kizhvac kampazitr]

thank you for all
here is the code I wrote
not allowed to use the ready function , so I wrote my

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::string reverse(std::string& s)
{
	std::string S;
	for(int i = s.size() - 1; i >= 0; --i)
		S += s[i];
	return S;
}

void sort_nd_make_palindrome(std::string& s)
{
	std::vector<int> buckets(26);
	for(int i = 0; i < s.size(); ++i)
		++buckets[s[i] - 'a'];
	s.clear();
	for(int i = 0; i < buckets.size(); ++i)
		for(int j = 0; j < buckets[i]; ++j)
			s.push_back(i + 'a');
	int index = -1;
	std::string begin;
	for(int i = 0; i < buckets.size(); ++i) 
		if(buckets[i]%2 != 0) 
		{
			if(index < 0)
				index = i;
			else 
				s = "impossible";
        }
	for(int i = 0; i < buckets.size(); ++i) 
		for(int j = 0; j < (buckets[i] / 2); ++j)
			begin += i + 'a';
	std::string middle;
	if(index >= 0) 
		middle += 'a' + index;
	s = begin + middle + reverse(begin);
}

int main()
{
	std::string letters;
	std::cin >> letters;
	sort_nd_make_palindrome(letters);
	std::cout << letters;
}