Palindrome Reorder

GitHub link

This is the twelfth problem in the CSES problem set.

The problem goes like this: Given a string determine if it's possible to reorder the letters such that it forms a palindrome. If it is possible, do so.

The first step of this problem is determining if it's possible to form a palindrome from the string. If you consider that properties of a palindrome, you'll realize that only one letter can occur an odd number of times. The first step of our code is to count the frequency of every letter and store it in an array. Then we traverse this array and stop the program if more than 1 letter occurred an odd number of times.

Now that we know that a palindrome can be formed and have the frequency of each letter, the next step is pretty easy. We just need to loop through our array, and for all but the letter that appears and odd number of times, output each letter half the number of times that it appeared in the original string. Then we output our odd letter so it's in the middle. Finally, we can loop back through the array in reverse and output each letter half the number of times that it appeared in the original string again. This fully outputs our palindrome.

While this solution works, it ran out of time on 4 test cases. After a little bit of research, it appeared that the reason for this is because Java is extremely slow when adding together substrings, and I was treating the final output as a string. In order to fix this I could either output the final string one char at a time, use a library like stringbuilder, or rewrite my program in C++. In order to be safe, I rewrote my program in C++ and was able to stay under the time limit with ease. Here's the code for this problem:

for(char c : a)
{
    freq[c - 'A']++;
}

for (int i = 0; i < 26; i++)
{
    if (freq[i] % 2 != 0)
    {
        oddCount += 1;
        oddInd = i;
    }
}
if (oddCount > 1)
{
    cout << "NO SOLUTION";
    return 0;
}
else
{
    for(int i = 0; i < 26; i++)
    {
        if (freq[i] % 2 == 0)
        {
            for (int j = 0; j < freq[i] / 2; j++)
            {
                cout << (char)(i + 'A');
            }
        } 
    }
    if (oddInd != 100)
    {
        for (int i = 0; i < freq[oddInd]; i++)
        {
            cout << (char)(oddInd + 'A');
        }
    }
    for (int i = 25; i >= 0; i--)
    {
        if (freq[i] % 2 == 0)
        {
            for (int j = 0; j < freq[i] / 2; j++)
            {
                cout << (char)(i + 'A');
            }
        }
    }
}

Entry written on 8/7/2022