3517. Smallest Palindromic Rearrangement I

medium · string · sorting · counting-sort · solved 2026.07.28 · 30 sec read

C++

class Solution {public:    string smallestPalindrome(string s) {        std::array<int, 26> stuff;        for (int i = 0; i < s.size(); i++) {            stuff[s[i] - 'a']++;        }        std::string output1 = "";        std::string output2 = "";        std::string output3 = "";        for (int i = 0; i < 26; i++) {            for (int j = 0; j < stuff[i] / 2; j++) {                output1 += i + 'a';                // output2 = static_cast<char>(i + 'a') + output2;            }            stuff[i] -= stuff[i] / 2 * 2;        }        for (int i = 0; i < 26; i++) {            for (int j = 0; j < stuff[i]; j++) {                output3 += i + 'a';            }        }        output2 = output1;        std::reverse(output2.begin(), output2.end());        return output1 + output3 + output2;    }};

I found this one simple, through through that palindrome need to be solved to half way point. then to just make string up to that. then reverse and then add. I had a memory exceeded issue with the output2 solving issue, it might have been from the static cast but just making a copy later in the code and then adding that together worked.

C++

class Solution {public:    string smallestPalindrome(string s) {        int n = s.length();        sort(s.begin(), s.begin() + n / 2);        for (int i = 0; i < n / 2; i++) {            s[n - 1 - i] = s[i];        }        return s;    }};

looking at this other solution I found, I realize that this was much simpler. First save space on editing the same string. then just sort part of the string and copy that to the other side.